基于满Steiner树问题的水下无线传感器网络拓扑愈合算法研究

启发式进化规划求解Steiner树问题
郭伟;席裕庚;全亚斌
【期刊名称】《上海交通大学学报》
【年(卷),期】2001(35)8
【摘要】求解 Steiner树对通信网络点对多点路由优化问题有重要意义 ,已被证明是 NP- complete的 .通过把图形简化技术、进化规划方法和 KMB启发式算法相结合 ,提出了一种求解 Steiner树问题的新方法 ,提高了算法的效率 .仿真结果表明 ,本算法是有效的 ,性能优于传统的启发式算法 .
【总页数】3页(P1152-1154)
【关键词】Steiner树;NP-complete;进化规划;KMB启发式算法;多点路由;网络资源优化
【作者】郭伟;席裕庚;全亚斌
【作者单位】上海交通大学自动化研究所
【正文语种】中文
【中图分类】TN919.8;TN911.1
【相关文献】
1.求解广义最小生成树问题的元启发式算法 [J], 王璨璨;徐进澎
2.基于进化规划求解最优通信生成树 [J], 曲润涛;席裕庚;韩兵
3.双层过道布置问题的混合整数规划模型及启发式求解方法 [J], 管超;张则强;毛丽丽;李六柯
4.基于进化计算的度约束最小生成树问题求解算法 [J], 万军洲
5.基于进化规划求解Steiner Tree问题 [J], 曲润涛;席裕庚;韩兵
因版权原因，仅展示原文概要，查看原文内容请购买。

基于AUVs的水下移动无线传感器网络愈合算法梁文辉;董强;何明;陈秋丽;丁晨璐【期刊名称】《计算机工程与应用》【年(卷),期】2015(000)019【摘要】水下移动无线传感器网络（MUWSNs）动态演化特性制约着网络的拓扑的可靠性，很大程度上限制了MUWSNs的推广应用。

针对水下实体移动导致的MUWSNs拓扑失效，提出了一种基于自主式水下航行器（AUV）的MUWSNs 拓扑愈合算法，并构建了水下实体移动模型，利用AUV自主移动特性对失效拓扑进行快速愈合。

仿真结果验证了该算法的正确性和有效性，极大地提高了MUWSNs可靠性，对MUWSNs拓扑领域研究具有一定贡献。

%The dynamic evolution features of Mobile Underwater Wireless SensorNetworks(MUWSNs)restrict the reli-ability of network topology, which restrains the generalized application of MUWSNs to a great extent. A new topology healing algorithm based on Autonomous Underwater Vehicles(AUVs)is proposed for restoring topology failure of MUWSNs caused by mobility of underwater entities. It constructs a mobility model used to simulate the motion of underwater entities. Taking advantage of the autonomous mobility feature of AUVs, the topology failure of MUWSNs can be restored rapidly. The experimental results show that this algorithm is correct and effective, immensely enhancing the reliability of MUWSNs, and making a great contribution to the research area of MUWSNs’topology.【总页数】5页(P98-102)【作者】梁文辉;董强;何明;陈秋丽;丁晨璐【作者单位】解放军理工大学指挥信息系统学院，南京 210007; 解放军61345部队;解放军理工大学指挥信息系统学院，南京 210007;解放军理工大学指挥信息系统学院，南京 210007;解放军理工大学指挥信息系统学院，南京 210007;解放军理工大学第六十三研究所，南京 210007【正文语种】中文【中图分类】TP393【相关文献】1.基于主从同步的欠驱动AUV与移动平台水下对接控制 [J], 刘俊杰;陈虹;王磊2.基于满Steiner树问题的水下无线传感器网络拓扑愈合算法研究 [J], 刘林峰;刘业3.AUV辅助的水下无线传感器网络模糊功率拓扑控制算法 [J], 任文豪; 郝琨; 赵璐4.AUV辅助的水下无线传感器网络模糊功率拓扑控制算法 [J], 任文豪;郝琨;赵璐5.基于卷积神经网络的AUV水下识别算法设计与实现 [J], 李昱;王俊雄因版权原因，仅展示原文概要，查看原文内容请购买。

基于粒子群算法的水下无线传感器网络路由策略研究刘守齐;张潮;冯锋【摘要】针对水下无线传感器网络能量消耗不均衡及生命周期短的问题,文章在LEACH协议的基础上提出了一种降低节点能耗,延长网络生命周期的水下路由协议算法.该协议将粒子群算法用于水下无线传感器网络的簇首路由优化中,同时考虑到节点的剩余能量、簇首节点到基站的距离和非均匀分簇等5个因素,确定最优传输路径,达到降低节点能耗,延长网络生存周期的目标.仿真结果表明,该协议极大地降低了网络能耗,提高了网络生存周期.【期刊名称】《江苏科技信息》【年(卷),期】2019(036)012【总页数】4页(P41-44)【关键词】水下无线传感器网络;粒子群算法;非均匀分簇;路由协议【作者】刘守齐;张潮;冯锋【作者单位】宁夏大学信息工程学院,宁夏银川 750021;宁夏大学信息工程学院,宁夏银川 750021;宁夏大学信息工程学院,宁夏银川 750021【正文语种】中文【中图分类】TP2120 引言随着海洋经济的发展以及世界各国对海洋权益的日益重视，水下无线传感器网络（Underwater Wireless Sensor Network，UWSN）作为一种新型无线传感器网络技术正在受到人们的普遍关注，并用在环境监测、海洋数据采集、海难预防等方面具有广泛的应用前景。

水下无线传感器网络是通过潜艇或水面舰艇将大量的传感器节点布置到目的水域，形成的一个无线自组织网络［1］。

由于水下传感器网络部署环境的特殊性、水声通信方式的高时延性和易受干扰以及人工作业等因素，使得水下无线传感器网络的能耗性和网络生存时间方面存在着极大的挑战［2］。

因此，低功耗的路由优化策略是水下无线传感器网络的重要研究方向。

目前，有很多国内外学者做过类似的研究。

例如，Yan等［3］提出了基于深度信息的网络路由策略，该算法设定只有当节点深度小于给定的深度值时才可以进行转发，但能耗方面依旧未得到很好的改善。

传感器网络中基于直骨架的连通性修复策略章红艳; 汪晓丁; 吴文焕【期刊名称】《《福建师大福清分校学报》》【年(卷),期】2019(000)005【总页数】7页(P24-29,57)【关键词】网络有效性; 连通性修复; 直骨架【作者】章红艳; 汪晓丁; 吴文焕【作者单位】福建师范大学协和学院福建福州 350117; 福建省网络安全与密码技术重点实验室福建福州 350007; 福建师范大学数学与信息学院福建福州 350117; 福建江夏学院福建福州 350108【正文语种】中文【中图分类】O240 引言无线传感器网络1-连通性修复问题往往被模型化成斯坦纳最小树(Steiner Minimal Tree SMT)问题，即利用较少的资源（如中继节点等）在各连通分支之间构造一棵最短内接树.由于中继节点部署间隔为R，则需要个中继节点，其中L 为内接树长度.这意味着内接树越短所需的资源也越少，即越接近最优的SMT.目前关于网络1-连通性修复的策略并没有将图形的几何性质与网络的拓扑结构很好地结合，因此难以用最少的中继节点完成1- 连通性的修复.论文利用较好图形几何性质的直骨架设计出了一种高效的无线传感器网络连通性修复策略RSS(Restoration strategy based on Straight Skeleton).该算法通过反复构造直骨架从而减少了连通性修复所需的中继节点数，并且从理论上证明了策略RSS 的近似比和复杂度分别为与O(n logn)，而仿真实验表明该策略在中继节点消耗上明显少于其他同类型策略.1 国内外研究现状现有的1-连通性修复策略中一部分（文献[1-11]）以近似比作为衡量标准，近似比越小那么算法的性能越好，而另一部分（文献[12-14]）则采用仿真实验来验证算法性能.Chen[11]提出近似比为3 的基于四边形的修复算法.Cheng[8]分别提出基于三角形的与基于3-超图的修复算法，并证明其近似比分别为3 和2.5.Lloyd[9]提出一种近似比在67 之间的斯坦纳化MST 算法.Tang[10]利用网络分簇构造修复算法，其近似比为4.5.Efrat[3]、Yang[6]、Misra[5] [7]等对于节点与节点、节点与中继、中继与中继这三种不同连接方式并结合目前最优的最小权斯坦纳树构造算法[15]，提出近似比分别为3.11、6.43、6.2 和12.4 的修复算法.Wang等[4]提出了一种结合Voronoi 图和重心的算法.近期，Wang 等[1]、Lalouani 等[2]先后提出在网络中存在障碍物情况下基于直骨架的修复算法.Ranga[13]提出一个基于0 梯度点的修复算法.Joshi[12]利用网络的直骨架并结合节点的传输半径，规划出一条最优的中继节点部署路线.陈洪生等[14]给出了一个基于四边形的连通度修复算法.相比于上述策略，论文所提出的策略RSS不仅近似比是最优的，而且复杂度也仅为O(n logn).表1 给出了RSS 与目前已知算法在近似比和复杂度方面的对比.表1 各算法在近似比和复杂度方面的对比作者近似比复杂度Misra et al.12.4O(n2k-2+n2k+1logn)Lloyd et al.7 O(n logn)Yang et al.6.43 O(n2k-2+n2k+1logn)Misra et al.6.2 O(n2k-2+n2k+1logn)Tang et al.4.5 无Efrat et al.3.11 O(n2k-2+n2k+1logn)Cheng et al.3 O(n4)Chen et al.3 O(n3)Wang et al.3 O(n3)Wang et al.images/BZ_30_1185_1725_1257_1771.png/3O(n3)Lalouani et al.images/BZ_30_1185_1796_1257_1842.png/3O(4n)Cheng et al.2.5 O(n3)RSS (本文)images/BZ_30_1198_1952_1282_2038.pngO(n logn)2 预备知识定义1.已知多边形P={p1,p2,...,pn-1,pn}(如图1 所示)，各顶点Pj 沿着其邻边夹角的平分线向P 内部等速移动所形成的直线轨迹构成了P的直骨架S(P).其过程会发生两类事件：边事件和分裂事件.边事件是指多个顶点在缩进的过程中会合成一点从而多个多边形的边消失成点；分裂事件是指凹顶点在缩进过程中将对边分割成两条边，从而原多边形被分裂成多个多边形.图1 多边形直骨架3 系统模型将无线传感器网络映射成图G＝{V，E}，其中V 为点的集合，而E 为边的集合.其中，每一个点代表无线传感器网络中的一个节点，而每一条边E 代表任意一对距离小于R 的节点链路.对于失去连通性的无线传感器网络，以半径R 为间隔部署中继节点来修复网络的连通性.以下给出论文所解决问题的形式化描述：给定一个具有|V|=n 个节点的图G，设计一种消耗中继节点数量最少的能实现n 个节点连通的连接方式.针对此问题，提出了一种高效的无线传感器网络连通性修复策略RSS(Restoration strategy based on Straight Skeleton).4 RSS 策略该策略通过7 步来实现无线传感器网络1-连通性的修复，具体执行步骤如下.4.1 对图G 生成最小生成树MST，并从一点开始沿着MST 对每个节点编号；4.2 从编号1 节点开始，每四个点分为一组ti，使得组与组之间没有共同点；如果剩下的点数小等于3，则将这些点分成一组，依次将ti 加入集合T，即;4.3 对于任意一个ti ∈T，如果|ti|=3，则至少重复执行以下步骤k=(ni-1)-2 次来构造最短内接树，其中ni 表示ti 中节点个数而和SMTtik分别指ti在第k次迭代生成的三角形、史坦纳点与直骨架：a.设边ei 和ej 为中最长的两条边，将ei、ej 与其相关联的史坦纳点组成三角形并在此三角形上构造第k 轮的直骨架；b. 将边ei 和ej 从中删除，即，并记k=k+1，然后返回步骤a.4.4 对于任意一个gi ∈T，如果，则重复执行以下步骤k 次来构造最短内接树，其中ni 表示ti 中节点个数而和分别指ti 在第k 次迭代生成的四边形、两个史坦纳点与直骨架：a.设边中与两个史坦纳点和关联的最长边，将与组成四边形并在这个基础上构造第k 轮的直骨架；b.将边与sisj从中删除，即，并记k=k+1，然后返回步骤a.4.5 对于每个分组ti，将k 次迭代中每次生成的直骨架连接成关于ti 的最短内接树，即；4.6 通过G 的最小生成树MSTG 构造图SMTG，使得SMTt|T|，对于任何一个圈Ci ∈SMTG，如果存在边ei ∈Ci使得对于所有的j，1 ≤≤ j ≤≤ |T|，都有ei∉SMTtj，则删除边ei ，即SMTG =SMTG\{ei}，那么SMTG 为所求最短内接树；4.7 在SMTG 上以R 为间隔部署中继节点.给出一个RSS 修复无线传感器网络连通性的例子.图2(a)给出了一个由11 个节点s1,s2,…,s11 组成的网络G.图2 一个RSS 示例首先对G 生成最小生成树，沿该生成树以最多四个节点为一组分成三组，如图2(b)中所示.在图2(c)中，对于分组G1 与G2 反复构造基于四边形的直骨架，对于分组G3 反复构造基于三角形的直骨架，在此过程中删除环边.在图2(d)中，每个中继节点以半径R 为间隔排列在最后生成的最短内接树上.5 理论分析在这节中，将对策略RSS 在近似比与复杂度方面进行分析.定理1 设的三条边ei、ej 与ek 中最长两条边ei与ej，当时，函数最大，其中x=L(ei)+L(ej)，y=L(ek).证明：根据题设，要使最大则需满足以下最优化公式，即：这可采用拉格朗日乘子法求解，令λ1、λ2为拉格朗日乘子，η为松弛变量，则有：即，当时f(x,y)最大，且有.证毕.定理2 设SMTtik-的四条边ei、ej、ek、el 与em 中最长三条相邻边ei、ej 与ek，当时，函数最大，其中x=L(ei)+L(ej)+L(ek)，y=L(el+em).根据定理1，易验证定理2 的正确性.对于任意一个三角形ti，第k-1 轮的最短内接树SMTtik-1的最长边 tik-1 ei =sis 与ej =sjstik-1生成的三角形tik-1 = ei∪ej ∪si sj将用于第k 轮最短内接树的生成.同理，四边形ej ∪ek ∪sisj 将用于第k 轮最短内接树的生成，其中，.由文献[1]可得，多边形最短内接树长度约为其最小生成树长度的.令为第k 轮迭代后ti 最短内接树长度，那么有，那么对于一个图G，有以下两个定理成立.定理3 设，，则，其中边ei 与ej 为SMTtik-1的两条最长边.定理4 设，则，其中边ei、ej 与ek 为SMTti'k-1的最长三条相邻边.通过归纳假设法易验证这两个定理的正确性.定理5 策略RSS 的近似比为.证明：Cheng [8]证明了史坦纳化三角形结合最小生成树的算法其近似比为3.而图G 的最短内接树SMTG =∪SMTti∪MSTG\C，其中C 代表策略RSS 中所需要删除边的集合.由于RSS 所需要的节点个数约为，根据定理1、2、3 和4，可得RSS的近似比为.证毕.定理6 策略RSS 的复杂度为O(n logn).证明：策略RSS 通过7 步完成对图G 的连通性修复，我们将依次分析每个步骤的复杂度从而得到其总体的复杂度.第1 步，图G 的最小生成树构造其复杂度为O(n logn)，其中n 代表图G 的节点个数.第2 步，分组的选择可在O(n)时间内完成.第3 步与第4 步，对于每一个分组最多通过次迭代构造最短内接树，在此步骤中每次迭代的复杂度不超过O(ni logni)，其中ni ∈3,4 .由于n=ni，则所有内接树构造的总复杂度不超过O(n).步骤5、6与7都可在常数时间内完成.因此，策略RSS 的复杂度为O(n logn).证毕.6 仿真实验在本节中，对策略RSS、RRLC-GBP[13]和OASS[1]三种策略进行比较.首先，50～70 个节点将被随机部署在一个的区域内.然后，分别通过固定节点个数变化半径的方式和固定半径变化节点个数的方式比较3 种策略平均所需中继节点的数量. 如图3 和4 所示，各策略所需中继节点数随着节点半径的增加而减少.RSS 所需的中继节点数量明显少于其他策略.图3 节点个数为50 时，各算法比较图4 节点个数为70 时，各算法比较如图5 所示，当中继节点半径等于50m时，各策略所消耗的中继节点数量随着节点数的增加而增加.RSS 消耗的中继节点数量最少.图5 半径等于50m时，各算法比较图6 可见，当中继节点半径增加到100m时，其消耗数量随着节点个数的增加呈现出先增后减的趋势.这是由于在固定大小的部署区域中，如果半径越大节点数量越多，则更多的节点直接相连.这意味着需要更少的中继节点.很明显的，RSS 所需的中继节点数量是最少的.图6 半径等于100m时，各算法比较7 总结连通性修复是利用较少的资源(如中继节点等)在各连通分支之间构造一棵最短内接树，而内接树越短所需的资源也越少.目前关于1-连通性修复的策略没结合图形的几何性质与网络的拓扑结构，因此难以用最少的中继节点完成修复.论文利用直骨架设计了一种高效的网络连通性修复策略RSS.该策略通过反复构造直骨架减少连通性修复过程中所需的中继节点数，并且从理论上证明了策略RSS 的近似比和复杂度分别为与O(n logn)，而仿真实验表明该策略在中继节点消耗上明显较少.【相关文献】[1] Xiaoding W,Li X,Shuming Z.A Straight Skeleton Based Connectivity Restoration Strategy in the Presence of Obstacles for WSNs[J].Sensors,2017,17(10)：2299.[2] Lalouani W,Younis M,Badache N.Optimized Repair of a Partitioned Network Topology[J].Computer Networks,2017,128：63-77.[3] Efrat A,Fekete S P,Mitchell J S B,et al.Improved approximation algorithms for relay placement[J].ACM Transactions on Algorithms(TALG),2016,12(2)：20.[4] Xiaoding W,Li X,Shuming Z.Restoration strategy based on optimal relay node placement in wireless sensor networks[J].International Journal of Distributed SensorNetworks,2015,11(7)：409085.[5] Misra S,Majd N E,Huang H.Approximation algorithms for constrained relay node placement in energy harvesting wireless sensor networks[J].IEEE Transactions on Computers,2014,63(12)：2933-2947.[6] Yang D,Misra S,Fang X,et al.Two-tiered constrained relay node placement in wireless sensor networks：Computational complexity and efficient approximations[J].IEEE Transactions on Mobile Computing,2012,11(8)：1399-1411.[7] Misra S,Hong S D,Xue G,et al.Constrained relay node placement in wireless sensor networks：Formulation and approximations[J].IEEE/ACM Transactions onNetworking(TON),2010,18(2)：434-447.[8] Cheng X,Du D Z,Wang L,et al.Relay sensor placement in wireless sensornetworks[J].Wireless Networks,2008,14(3)：347-355.[9] Lloyd E L,Xue G.Relay Node Placement in Wireless Sensor Networks[J].IEEE Transactions on Computers,2007,56(1)：134-138.[10] Tang J,Hao B,Sen A.Relay node placement in large scale wireless sensornetworks[J].Computer communications,2006,29(4)：490-501.[11] Chen D,Du D Z,Hu X D,et al.Approximations for Steiner trees with minimum number of Steiner points[J].Journal of Global Optimization,2000,18(1)：17-33.[12] Joshi Y K,Younis M.Exploiting skeletonization to restore connectivity in a wireless sensor network[J].Computer Communications,2016,75：97-107.[13] Ranga V,Dave M,Verma A K.Relay node placement to heal partitioned wireless sensor networks[J].Computers &Electrical Engineering,2015,48：371-388.[14] 陈洪生,石柯.基于四边形斯坦纳树的无线传感器网络连通恢复[J].计算机学报,2014,37(2)：457-469.[15] Robins G,Zelikovsky A.Tighter bounds for graph Steiner tree approximation.SIAM Journal on Discrete Mathematics[J].2005,19(1)：122-134.。

基于n层二叉树的水下无线传感器网络路由算法的设计孔德川;王建平;牛立元【摘要】基于超声波进行通信的水下无线传感器网络很难采用陆地上使用的无线传感器网络路由算法.提出了一种基于n层二叉树的水下无线传感器网络路由算法的设计过程,基于三维空间坐标来对水下传感器节点进行定位,采用最接近水平轴的策略来选择最远邻居,利用传感器彼此间的深度差来决定路由方向,通过多跳方式,基于多路径进行数据传输.通过MATLAB实现了算法的性能仿真,分别探讨了不同层数和传输半径的影响,实验结果显示,二叉树的层数越高,传输半径越大,其数据包传递率越高.通过传输半径为100m的3层二叉树算法对比了DBR、ECBP和Hydrocast3种路由算法的数据包传递率和能耗情况.结果显示,该算法具备较高的数据包传递率,而能耗相对较低.在实际水下传感器网络应用中,选择合适传输半径和层数的二叉树路由算法,实现数据包传递率和能耗的折中,是未来研究的热点问题.【期刊名称】《仪表技术与传感器》【年(卷),期】2014(000)006【总页数】5页(P133-137)【关键词】n层二叉树;路由算法;水下无线传感器网络;超声波通信;数据包传递率;信号传输半径【作者】孔德川;王建平;牛立元【作者单位】河南科技学院,河南新乡453003;河南科技学院,河南新乡453003;武汉理工大学,湖北武汉430070;河南科技学院,河南新乡453003【正文语种】中文【中图分类】TP212.9;TP391.90 引言水下无线传感器网络通常由大量的传感器组成，传感器随机分布在水下感测区域内，用来侦测环境的变化或者感应其目标物，并将收集的数据做处理，以声波传输的方式，传送到汇聚节点或海上基站。

水下无线传感器网络是由具有声学通信与计算能力的传感器节点构成的水下监测网络系统[1]。

随着无线传感器技术的发展，当前水下无线传感器网络的研究已经引起了学术界的高度重视。

针对水下无线传感器网络的系统结构、水下定位、水声通信等研究领域已经开展了大量基础研究，并取得了一定的成果，相关小规模的海洋传感器网络已经投入试验运行[2]。

基于四边形斯坦纳树的无线传感器网络连通恢复陈洪生;石柯【期刊名称】《计算机学报》【年(卷),期】2014(037)002【摘要】在恶劣环境下无线传感器网络的节点和通信链路常常会失效,致使网络被分割为很多分离的分区,因此通过布置尽量少的中继节点实现高健壮性的连通恢复对于维持网络的正常运作必不可少.对于一个被分割的无线传感器网络,找到相应的位置布置最少中继节点恢复连通是一个NP难题,在实际应用中只能采用启发式算法.文中提出了一种新的基于四边形斯坦纳树的算法来恢复网络连通.此算法首先探测出各分区并确定各分区的代表节点及其位置,然后寻找合适的四边形连接分割的网络分区,确定这些四边形的斯坦纳点;对无法用四边形连接的各连接部分用三角形斯坦纳树或最小生成树的方法连接;最后沿着斯坦纳树的边在相应位置布置中继节点,实现网络连通的恢复.大量的仿真实验表明文中提出的方法能够减少所需中继节点的数量,恢复后的拓扑结构中节点的连通度更高,容错性更好.【总页数】13页(P457-469)【作者】陈洪生;石柯【作者单位】华中科技大学计算机科学与技术学院武汉430074;湖北科技学院计算机科学与技术学院湖北咸宁437005;华中科技大学计算机科学与技术学院武汉430074【正文语种】中文【中图分类】TP393【相关文献】1.基于三角形斯坦纳树的分区连通性恢复算法 [J], 秦宁宁;吴德恩;余颖华2.考虑障碍的无线传感器网络连通性恢复策略 [J], 马桂真;于平3.移动无线传感器网络连通性自主恢复算法 [J], 马桂真;于平4.无线传感器网络连通恢复综述 [J], WU Chun-hui;CHEN Hong-sheng5.基于斯坦纳树和泰森多边形的连通恢复算法 [J], 王茂秋;张江;张晶因版权原因，仅展示原文概要，查看原文内容请购买。

收稿日期:2006-02-13;修订日期:2006-04-18 基金项目:国家自然科学基金(60273041) 作者简介:吴春婧(1979-),女,山东临沂人,硕士研究生,主要研究方向:传感器网络路由;　秦继林(1981-),女,内蒙古丰镇人,硕士研究生,主要研究方向:组播路由;　郑明春(1964-),女,山东济南人,教授,博士,主要研究方向:无线网络、传感器网络、QOS 组播.文章编号:1001-9081(2006)08-1793-03传感器网络中一种基于数据融合树的低功耗路由算法吴春婧1,秦继林1,郑明春2(1.山东师范大学信息科学与工程学院,山东济南250014;2.中国科学技术大学计算机科学技术系,安徽合肥230026)(wcjg m @ )摘　要:针对传感器网络节点资源有限的特点,结合最小Steiner 树的概念,提出了一种基于数据融合树的路由算法,该算法通过快速构造最小生成树来建立一个虚拟骨干网,使得数据高效的传输。

理论分析和模拟实验也表明该算法具有很好的节能性。

关键词:数据融合;路由;Steiner 树;虚拟骨干网中图分类号:TP393.03 文献标识码:AL ow power routi n g a lgor ith m ba sed onda t a 2aggrega ti on tree for sen sor networksWU Chun 2jing 1,Q I N J i 2ling 1,ZHE NG M ing 2chun2(1.School of Infor m ation Science and Engineering,Shandong N or m al U niversity,J inan Shandong 250014,China;2.D epart m ent of Co m puter Science and Technology,U niversity of Science and Technology of China,Hefei A nhui 230026,China )Abstract:W ith regard t o the li m ited res ources of nodes in sens or net w orks,a ne w l ow power r outing algorith m based on data 2aggregati on tree combining the concep t of the s mallest Steiner tree was p r oposed .This algorith m could i m p r ove the data trans m issi on thr ough fast establish ment of a virtual backbone net w ork .Theoretic analysis and si m ulati on results show that the algorith m can be more energy 2saving .Key words:data aggregati on;r outing;Steiner tree;virtual backbone net w ork0　引言与传统的网络相比,传感器网络节点数量巨大,分布稠密,并且节点探测到的数据可能有冗余的信息,在传送数据的时候可能消耗很多的能量。

CN43-1258/TP ISSN1007-130X计算机工程与科学Computer Engineering&Science第42卷第8期2020年8月Vol.42,No.8,Aug.2020文章编号：1007-130X(2020)08-1352-07基于斯坦纳树和泰森多边形的连通恢复算法!王茂秋X张江张晶134(!昆明理工大学信息工程与自动化学院，云南昆明650500；2.中国船舶集团有限公司第七O五研究所昆明分部，云南昆明650102；3.云南枭润科技服务有限公司，云南昆明650500；4.昆明理工大学云南省人工智能重点实验室，云南昆明650500)摘要：针对无线传感器网络容易遭受恶劣环境破坏，连通恢复后各关键节点的能量损耗远大于其他节点从而导致网络断连的问题,提出基于斯坦纳树和泰森多边形的连通恢复算法(CRAST)。

首先，将被分割的节点分区抽象为离散点，枚举出离散点区域内的所有非退化四边形，再使用四边形斯坦纳树结构对这些非退化四边形部署中继节点以达到连通恢复。

然后，用关键节点构建Delaunay三角网，通过Delau-nay三角网构建出整个无线传感器网络的泰森多边形拓扑结构$最后，在泰森多边形所有顶点部署可移动的备用中继节点，在关键节点损坏时通过比较备用节点所占关键节点对应的所有备用节点比重选择要移动的备用节点，移动备用中继节点替换损坏的关键节点。

整个算法能使传感器网络以最少的代价实现连通恢复，并且拥有较强的高效性和健壮性$关键词：连通恢复；斯坦纳树；泰森多边形；备用节点移动中图分类号:TP393文献标志码:Adoi：10.3969/j.issn.1007130X.2020.0&004A connectivity restoration algorithm basedon Steiner tree and Tyson polygonWANG Mao-qiu1,ZHANG Jiang2,ZHANG Jing13"(1.Faculty of Information Engineering and Automation,Kunming University of Science and Technology,Kunming650500；2.Kunming Branch of the705th Research Institute of China State ShipBuilding Co.,Ltd..Kunming650102；3.Yunnan Xiaorun Technology Service Co.,Ltd.,Kunming650500；4.Yunnan Key Laboratory of Artificial Intelligence,Kunming University of Science and Technology,Kunming650500,China)Abstract:Aiming at the problem that wireless sensor networks are susceptible to severe environmen­tal damage and the energy consumption of key nodes is fast after connectivity restoration,which leads to networkdisconnection"this paper proposes a network connectivity restoration(CRAST)algorithm basedonSteinertreeandTysonpolygon.Firstly"thealgorithmabstractsthedividednodepartitionsin-to discrete points,enumerates all non-degenerate quads in the discrete point area,and then uses the quadrangular Steiner tree structure to deploy relay nodes t o these non-degenerate quads so as t o achieve connec ivi yres ora ion.Secondly"he algori hm cons ruc s a Delaunay riangle ne work wi h key nodes"anduses he Delaunay rianglene work ocons ruc he Tysonpolygon opologyof heenire wirelesssensorne work.Fina l y"healgori hmdeploysmovablebackuprelaynodesa a l vericesof he Tysonpolygon"andmoves hebackuprelaynode oreplace hedamagedkeynodewhen hekeynodeis damaged.Thealgori hm enables hesensorne work oachieveconnec iviyrecoverya heleas cos"*收稿日期：2020-01-09；修回日期：2020-03-11基金项目：云南省技术创新人才资助项目(2019HB113)；云南省“万人计划”产业技术领军人才资助项目(云发改人事［2019*1096号)通信作者：张晶(1735335400@)通信地址650500云南省昆明市昆明理工大学信息工程与自动化学院..Address:Facul ty of Information Engineering and Automation,Kunming Universty of Science and Technology,Kunming650500, Yunnan,P.R.China王茂秋等：基于斯坦纳树和泰森多边形的连通恢复算法1353and has strong efficiency and robustness.Key words：connectivity restoration；Steiner tree；Tyson polygon；standby node movement1引言在信息化时代，实时掌握指定区域内状态的技术常被应用到军事、气象等多个领域1,作为计算机网络中最重要的技术，无线传感器网络也得到了前所未有的发展。

无线传感器网络拓扑修复算法综述王晓璇;王珺;贾莹莹;张鑫【摘要】在无线传感器网络中,由于能量耗尽以及恶劣环境的影响,传感器节点容易出现故障导致网络不连通.为此,针对无线传感器网络中的拓扑修复问题,总结和分析近年来相关的主要方向和研究成果,同时根据网络故障规模的不同对小规模故障和大规模故障的网络修复算法进行分类总结以及优缺点分析.此外,从算法触发条件以及实现角度等方面对修复算法作进一步分类,并指出当前研究的不足和未来的改进方向.【期刊名称】《计算机工程》【年(卷),期】2018(044)008【总页数】7页(P93-99)【关键词】无线传感器网络;拓扑修复;连通性;邻居节点;Steiner树【作者】王晓璇;王珺;贾莹莹;张鑫【作者单位】南京邮电大学宽带无线通信与传感网技术教育部重点实验室,南京210003;南京邮电大学江苏省无线通信重点实验室,南京210003;南京邮电大学宽带无线通信与传感网技术教育部重点实验室,南京210003;南京邮电大学江苏省无线通信重点实验室,南京210003;南京邮电大学宽带无线通信与传感网技术教育部重点实验室,南京210003;南京邮电大学江苏省无线通信重点实验室,南京210003;南京邮电大学宽带无线通信与传感网技术教育部重点实验室,南京210003;南京邮电大学江苏省无线通信重点实验室,南京210003【正文语种】中文【中图分类】TP301.60 概述无线传感器网络(Wireless Sensor Network,WSN)[1]是由大量密集部署在目标区域的节点构成的一种自组织网络应用系统[2]。

该系统由大量小规模、低成本的传感器构成,将在目标区域采集到的数据汇集到基站[3]。

WSN起源于军事领域的应用,近年来,其在环境监测、医疗护理、火灾监测、交通监控等领域也得到广泛的应用[4]。

由于传感器自身资源及能量的限制,传感器节点易受到损坏,关键节点的损坏将导致网络被分割成不连通的分区,给实际应用带来不便。

一种以电性能优化为目标的Steiner树算法
洪先龙
【期刊名称】《计算机学报》
【年(卷),期】1995(018)004
【摘要】本文提出了一种以电性能优化为目标的Steiner树算法,它把从线网的源点到漏点的时间延迟最小作为求解Steiner树的目标.文中首先给出一种多端线网连线延迟模型,然后导出它的上界,它是线网连线总长和从源点到漏点路径长度的函数.用这个上界作为求解Steiner树的优化目标.算法采用了非线性优化技术和动态规划方法.实验例子表明,算法是十分有效的.
【总页数】7页(P266-272)
【作者】洪先龙
【作者单位】清华大学计算机科学与技术系,北京,100084
【正文语种】中文
【中图分类】TP3
【相关文献】
1.一种修复网络拓扑的Steiner树移动控制算法 [J], 闫中江;沈中;常义林;张颖;代亮
2.一种改进的Steiner树启发式算法 [J], 余燕平;仇佩亮
3.一种基于改进模拟退火算法的程序性能优化参数搜索算法 [J], 陆平静;李宝;易任娇;张英;王绍刚;庞征斌
4.多目标遗传算法求解认知无线电性能优化问题 [J], 王国强;李金龙;张敏;王煦法
5.一个以时延优化为目标的力指向Steiner树算法 [J], 洪先龙
因版权原因，仅展示原文概要，查看原文内容请购买。

专利名称：一种基于遗传算法的水下无线传感器网络拓扑控制方法
专利类型：发明专利
发明人：杨光,戴礼娥,毛玉明
申请号：CN202010030325.X
申请日：20200113
公开号：CN111246416B
公开日：
20220329
专利内容由知识产权出版社提供
摘要：本发明的基于遗传算法的水下无线传感器网络拓扑控制方法，包括：a).构建水下网络模型；b).建立成员节点、簇首节点能量模型及能量参数；c).计算最优簇首数量；d).采用遗传算法确定最优簇首，包括：d‑1).染色体编码；d‑2).选取初始种群；d‑3).构造适应度函数；d‑4).构造选择算子、交叉算子、变异算子；d‑5).计算个体适应度值；d‑6).选择最优簇首；e).自组成簇和进行数据通信。

本发明的水下无线传感器网络拓扑控制方法，在簇首选择阶段使用遗传算法，能够解决多目标优化问题，能够有效均衡能量和距离因素，能够有效均衡各节点能量消耗，降低了网络整体能耗，从而延长整个网络生存期。

申请人：山东交通学院
地址：250357 山东省济南市长清大学科技园海棠路5001号
国籍：CN
代理机构：北京华际知识产权代理有限公司
代理人：褚庆森
更多信息请下载全文后查看。

基于改进Steiner树的CRN双信道连通拓扑控制齐小刚;张丽敏;刘立芳【摘要】当认知无线电网络中的主用户活动时,网络连通性较差.针对该问题,结合功率控制和信道分配技术,提出使用最小数目信道构造双信道连通无冲突拓扑的方案.生成基本拓扑,使用图着色理论为每个次级用户分配信道.在此基础上,考虑到删除节点后局部冲突图可能不连通,利用改进MPH算法给最短路径密集经过的节点分配路径权值.同时为避免删除节点后拓扑被分为两部分,取切割部分点间最短距离的一半位置添加节点,从而实现双信道连通.理论分析和仿真结果表明,在任意主用户引起的单信道中断情况下,该方案能够保持网络连通,同时减少所需信道数和网络花费.【期刊名称】《计算机工程》【年(卷),期】2018(044)006【总页数】6页(P34-39)【关键词】认知无线电网络;拓扑控制;双信道连通;改进MPH算法;信道分配【作者】齐小刚;张丽敏;刘立芳【作者单位】西安电子科技大学数学与统计学院,西安710126;西安电子科技大学数学与统计学院,西安710126;西安电子科技大学计算机学院,西安710071【正文语种】中文【中图分类】TP3930 概述在认知无线电网络(Cognitive Radio Network,CRN)中,主用户(Primary User,PU)和次级用户(Secondary User,SU)共同存在。

PU是无线频谱的授权拥有者。

虽然SU没有授权接入频谱,但其被允许根据频谱可用概率机会式接入授权频段。

为了避免对PU的恶意干扰,SU在PU出现时必须归还频谱给PU。

因此,CRN中多个SU在PU取回授权信道时,不得不中断自己的数据传输或者切换到另外未被占用的频谱上进行。

因此,一个或者多个活跃PU的突然出现可能会切割整个CRN,特别在频谱切换阶段,会导致数据包丢失或者SU大量数据包时延[1-3]。

如何在考虑主用户活动性的情况下保持CRN的网络连通性,是CRN研究中的关键问题。