基于最小刚性图代数特性的无线网络拓扑优化算法-罗小元.pdf

《基于最小刚性图代数特性的无线网络拓扑优化算法-罗小元.pdf》由会员分享，可在线阅读，更多相关《基于最小刚性图代数特性的无线网络拓扑优化算法-罗小元.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、物理学报Acta Phys. Sin. Vol. 65, No. 24 (2016) 240201基于最小刚性图代数特性的无线网络拓扑优化算法 罗小元y李昊马巨海(燕山大学电气工程学院,秦皇岛066004)(2016年1月14日收到; 2016年7月23日收到修改稿)对于能量受限的无线传感器网络,拓扑优化能够降低能耗,优化通信链路结构.本文基于最小刚性图原理提出了一种新的拓扑优化算法,算法综合考虑了生成拓扑链路图中通信链路的权值与生成刚性图的代数特性问题,既保证了通信链路较短,有利于延长网络的生命周期,同时使生成的通信链路图结构更加稳定,网络具有较好的鲁棒性.仿真实验表明,与相关算法比较,提出

2、的算法中通信链路较短,具有较好的网络连通性与结构稳定性,同时生成刚性图矩阵的迹较大,具有较好的刚度代数性能.关键词:无线传感器网络,拓扑优化,最小刚性图,代数特性PACS: 02.10.Ox, 02.10.Yn, 02.10.v DOI: 10.7498/aps.65.2402011引言近年来,无线传感器网络得到了飞速的发展.相比于传统有线传感器网络,无线传感器网络的应用有助于对不可达或远程区域的精准监控,为人类认识物理世界架起新的桥梁.无线传感器网络在军事和民用领域有着广阔的应用前景,如军事侦察、环境监测、医疗监护、空间探索、城市交通管理、仓库管理1 3等.对于能量受限的无线传感器网络,拓扑

3、优化能够降低能耗,延长网络的生命周期,增强通信链路结构的稳定性,使网络更好地应用于复杂环境.研究人员已经提出了许多相关的拓扑优化算法4 6. Wattenhofer和Zollinger7提出异常拓扑控制(exotic topology control, XTC)算法不依赖于节点位置信息来构建拓扑,而是通过各链路的相对信号强度来构建拓扑,提高了算法在实际应用中的可行性,然而算法中处于拓扑边缘的节点通信链路结构稳定性不足. Chen8提出了四级分簇算法,考虑到了节点间的剩余能量问题,构建分级链路结构,提高了网络负载的均衡性.但是当生成簇较多时头节点的节点度会迅速增加,影响传感器的连通性.为加强算法

4、对环境的适应性, Qin等9提出了分布式的k-means算法和模糊c-means算法以优化分簇结构提高拓扑灵活度与鲁棒性.宋佳等10提出了一种针对多冗余通路的控制算法,提高了网络对于故障的预防能力.郝晓辰等11提出了一种健壮性可调的控制算法,引入节点调度调节因子并量化网络节点度,寻求节点度的取值规律,获得网络最优节点度,提高了网络结构的均衡性.基于刚性图的网络拓扑优化方法具有较好的网络连通性,并适用于较大规模的网络拓扑优化.方斌和陈特放12提出了一种基于最小刚性图的编队控制方法,对不同操作条件下刚性保持问题进行了研究.Luo等13提出了一种基于最优刚性图的最优刚性几何图自适应保真(optima

5、lly rigid geographicaladaptive delity, ORGAF)算法,考虑到传感器节点区域的布置,加入节点调度机制,重点优化了网络通信链路的权值,减少了节点发射与接收功率,国家自然科学基金(批准号: 61375105)资助的课题.通信作者. E-mail: 2016中国物理学会Chinese Physical Society http:/240201-1万方数据物理学报Acta Phys. Sin. Vol. 65, No. 24 (2016) 240201较好地延长了网络的生命周期.然而算法未考虑到刚性图代数特性的影响.文献14, 15研究发现网络控制与定位的刚度

6、特性与其代数性质密切相关. Anderson等16提出了基于刚性图刚度矩阵特性对网络定位的方法,在定位过程中,定位点的选择以及网络的构建中提高了生成网络的刚度矩阵特征值,在保证网络连通性的前提下提高了网络结构的稳定性.然而算法中未考虑链路权值对于网络寿命的影响.本文提出一种基于最小刚性图刚度代数特性优化的无线传感器网络拓扑控制算法(MRGAFU算法).该算法综合考虑了生成拓扑链路图中通信链路的权值与生成刚性图的刚度问题,既保证了通信链路较短,有利于延长网络的生命周期,同时使生成的通信链路图结构更加稳定,使网络具有较好的鲁棒性.2图论基础与问题描述2.1图论传感器网络的拓扑结构通常用图来描述.本

7、节将简要介绍本文所用到的一些基本图论知识.考虑一个由N个节点组成的无线传感器网络,其拓扑用无向图G(v;)表示,其中,顶点数集v = f1;2; ;Ng表示传感器节点,边集 = f(i;j) 2 v v : i = jg表示传感器节点之间的通信链路.顶点是由随机部署的传感器节点的位置pi 2 Rn决定的.对于任意节点i;j 2 v,若满足pi pj 6 Rc, Rc为节点的传输范围,则节点j是节点i的通信邻居.2.2最小刚性图本文算法中用到了两个重要概念:刚性图和最小刚性图,它们均属于无向图且是连通的.如果在保证各边长度不变的情况下,一个图不会发生形变,称此图为刚性图,否则称为可变形图.如果刚

8、性图删除任意一条边都会导致此图变成可变形图,则称此图为最小刚性图.易知,依据最小刚性图构建的拓扑结构是刚性的,具有较好的稳定性.图1给出了可变形图、刚性图和最小刚性图的例子.最小刚性图中每个顶点至少有两条邻接边17,因此,最小刚性图同时具有较小的通信复杂度和较强的鲁棒性.以最小刚性图结构建立的通信拓扑可以实现负载的均衡性,减少链路能量消耗,并延长网络寿命.(a) (b)(c)图1 (a)可变形图、(b)刚性图和(c)最小刚性图Fig. 1. (a) Deformable graph, (b) rigid graph and(c) minimum rigid graph.最小刚性图可通过刚度矩阵

9、来建立. n维刚度矩阵的构建过程如下:将图中顶点坐标按fp11; ;pn1;p12; ;pn2; ;p1N; ;pnNg顺序排列.建立一个其行与列分别对应边和顶点坐标的矩阵M 2 Rjj Nn,则矩阵M即为刚度矩阵.由文献16中的定理1可直接得到如下刚度矩阵的性质.引理1如果刚度矩阵M存在2N 3行元素构成的子矩阵满足rank(M) = 2N 3; (1)则由这2N 3行对应的边和N个顶点构成的图是最小刚性图.本文还需用到如下刚性图的替换引理.引理24如果已知刚性图G(v;)的一个子图G(v;)由任意其他刚性图子图G(v;)替代,则得到的图仍是刚性的.2.3刚性图的代数特性刚度矩阵可以完全通过

10、代数方式进行表述.对于一个平面二维网络(G;p),令顶点j的向量为pj = xj;yjT,刚度矩阵M可以由任意顺序的点与边表示,其中矩阵行数为jj,列数为2jvj.每条边对应矩阵的一行,同一边相连接的顶点j与顶点k的非零行向量在矩阵中第2j 1;2j;2k 1;2k列,240201-2万方数据物理学报Acta Phys. Sin. Vol. 65, No. 24 (2016) 240201对应可表示为xj xk;yj yk;xk xj;yk yj.刚度矩阵中的元素与节点间定位的绝对值无关,仅仅取决于节点间的相对位置.一个图是刚性的当且仅当由顶点关系得到的刚度矩阵的秩是2jvj 3时.刚度矩阵包

11、含很多图的刚度的定量信息,尤其是刚度矩阵的奇异值提供了一种测量网络代数性质的方法18.定义网络中边的刚度矩阵为X(G;P) = M(G;P)MT(G;P) 2 Rjj jj; (2)其中行列式具有较大特征值的刚性图具有更好的代数刚度特性.较好的刚度特性可以保证网络覆盖定位时具有较小的误差,进而提高网络的稳定性.最小刚性图的刚度矩阵特征值可以反映其结构特性,图2(a)与图2(b)是依据Henneberg序列4构建的两种不同结构的最小刚性图,当点B趋近于点A时,图2(c)中出现了可以自由移动的边AC,不再是刚性图,而图2(d)仍然可以保持刚性,可见右图具有较好的稳定性.经过计算可以发现图2(b)的

12、刚度矩阵特征值要大于图2(a)的刚度矩阵特征值,在定位与通信链路结构方面有着更好的性能.A EDBCA EDBCEDCEDCA BCA B(a) (b)(c) (d)图2两种不同结构的最小刚性图Fig. 2. Minimum graphs of two dierent structure.3基于最优刚性图的拓扑优化算法无线传感器网络是由许多小而能量受限的传感器节点组成的,优化通信链路、延长网络寿命一直是网络拓扑研究的重要方向之一.同时,针对一些较复杂的环境,如水下监测等,还需要考虑网络链路通信结构的鲁棒性.3.1算法构建刚度矩阵具有较大特征值的最小刚性图具有较好的代数刚度特性.同时,通信链路加

13、权较小的最小刚性图能较好地延长网络的寿命.为保持最小刚性图具有较好的代数刚度特性,就需要优化拓扑保持刚度矩阵具有较大的特征值.矩阵的迹是矩阵的特征值之和,因此保证刚度矩阵的迹较大,即可满足刚性图拓扑链路具有较好的结构稳定性.保持图是最小刚性图的条件下,使刚度矩阵迹值达到最大.该过程可转化为一个最优化问题:maximize trace(M(G;P)MT(G;P);subject to rank(M(G;p) = 2n 3: (3)该最优化问题可以通过经典的贪婪算法求解(表1),即在保证刚度矩阵秩为2n 3条件下,每一步构建最小过程中找出使构成的拓扑链路图的迹最大的边,加入到网络中.表1贪婪算法T

14、able 1. Greedy algorithm.Greedy algorithm1:选取集合表示来构建最小刚性图的边,并赋值为空集2: fe2cngnn未被选择的边3: while rank(M(G;p) 2n 3 do4: e = argmaxe2Of(feg) f()nn使刚度矩阵的迹最大化的边5: feg6: fe2cng7: end while8: 算法中考虑到网络生命周期,在构建最小刚性图过程中首先将边的长度按照升序排列,再依次选择其中使刚度矩阵迹最大的边加入到刚度矩阵中,即在保证网络刚性代数性能条件下进一步减小通信链路权值,优化拓扑链路结构.采用分布式算法可以减小网络构建的复杂度

15、.在构建刚性图网络拓扑中依据引理3,删除网络中所有不满足要求的边,生成网络拓扑链路图.240201-3万方数据物理学报Acta Phys. Sin. Vol. 65, No. 24 (2016) 240201引理313 Gi(i = 1;2; ;n)表述由顶点i及其所有邻接顶点组成的最小刚性图, G(V;E) =i=1;2; ;nGi, Gopt = (V;Eopt)表示生成的整体最小刚性图,则有如下结论:1) e /2 Eopt,如果对于两个顶点k;l 2 Gi;Gj,有e = (k;l) 2 Gj,但e /2 Gi;2)删除满足条件(1)的所有边得到的图是最小刚性图Gopt = (V;Eo

16、pt).依据上述引理,我们提出一个分布式算法来控制网络链路,得到链路拓扑结构,该算法程序见表2.表2最小刚性图生成算法Table 2. MRGAFU algorithm.MRGAFU algorithm1:任意活动节点i2v:初始化节点i的集合j ij和集合j ij为空2:节点i以最大传输半径广播包含其节点ID和位置信息的HELLO消息3: While点i收到来自节点u的HELLO_ACT消息do节点i将链路(i, u)添加到集合j ij4: end while5:计算节点i与其邻居Ni之间所有边的长度6:将这些边按照升序排列7:依据上述序列建立子图的刚度矩阵fMi8:初始化Mi,令Mi =M

17、i(1)9: for j = 1 : j j10: while rank(Mi) 6 2(jNij+ 1) 311:应用贪婪算法,依次比较使Mi迹最大的Mi(l;:)作为新的Mi(j + 1;:)12: Mi =24 MiMi(j + 1;:)3513: ifMi是满秩14:将此行对应的边记录到集合j j中15: end16: end17: end18: for u =fN;ig19: for v =fNi;i;u= vg20: if (u;v) /2 21:删除所有在 q(q2iNi)中记录的(u;v)22: end23: end24: end算法中综合考虑了链路权值及刚度矩阵迹的代数特性,

18、对网络进行拓扑优化,同时采用分布式的方法也可以降低算法复杂度.3.2算法分析本节针对算法的一些特性进行理论分析与证明.性质1网络中各个节点间都是2-连通的.证明根据本文算法,各节点组成的拓扑图是一个最小刚性图,而最小刚性图是属于刚性图的17,由2.2节中刚性图的性质可知,刚性图是连通的且每个顶点至少有两条邻接的边.可知,网络中节点间通信至少是2-连通的.证毕.性质2定义节点度为能与该节点直接通信的邻居节点的数量,则算法平均节点度收敛于4.证明MRGAFU算法是通过删除G(V;E)中不属于最小刚性图的边得到的,因而,其必定是最小刚性图,由引理1可知算法生成图中有2n 3条边,另外,根据图形边数与

19、节点度的关系易知节点度总和为边数的两倍,从而平均节点度可表示为D = 2 (2n 3)/n = 4 6/n,这意味着图的平均节点度随着节点数量的增加逐渐趋近于4.因此,此性质成立.证毕.4仿真实验本节采用Matlab软件进行仿真实验,验证算法有效性.将MRGAFU算法与最小刚性图拓扑(minimal rigid graph, MRG)算法19和具有较好连通性的几何图自适应保真(geographical adap-tive delity, GAF)算法20进行仿真比较,在10 m10 m区域内随机分布36个传感器节点得到的网络拓扑链路图如图3图5所示.0 2 4 6 8 100123456789

20、10图3 GAF算法拓扑链路图Fig. 3. Topological link graph of GAF.240201-4万方数据物理学报Acta Phys. Sin. Vol. 65, No. 24 (2016) 2402010 2 4 6 8 10012345678910图4 MRG算法拓扑链路图Fig. 4. Topological link graph of MRG.0 2 4 6 8 10012345678910图5 MRGAFU算法拓扑链路图Fig. 5. Topological link graph of MRGAFU.比较图中链路可以发现,图3图5中生成的拓扑链路中每个顶点至少

21、有两条边与其相连,说明通信时可以保证GAF算法与基于最小刚性图的MRG和MRGAFU算法中每个传感器节点至少有两条链路与其相连,具有较好的连通性,在复杂环境下抗干扰能力较强,同时有利于提高网络负载的均衡性.在无线传感器网络中,过高的节点度易导致信道间的串扰与冲突,数据包需要多次重传,这必然造成一些不必要的能量耗散.图6比较了GAF算法与MRGAFU算法的网络平均节点度.由图6可知, GAF算法在网络分布节点较多时,平均节点度会高于MRGAFU算法的结果,而MRGAFU算法的平均节点度趋近于4,这个特性减少了许多不确定因素,如节点密度对最终优化的拓扑的影响,使得由MRGAFU算法得到的拓扑有了一

22、定的独立性和可预测性.同时,在实际应用中,可预测的网络平均节点度为有限的网络资源的分配提供了一定的参考依据,一定程度上提高了资源的利用效率.50 100 150 200 250 300 350 400051015BBGAFMRGAFU图6拓扑后的网络平均节点度情况Fig. 6. Network average node degree of the topology.图7和图8统计了基于最小刚性图拓扑的MRG算法与MRGAFU算法下构建的最小刚性图中生成拓扑图的刚度矩阵的迹以及链路图的链路权值.由图7可知,相同环境下采用MRGAFU算法构建的最小刚性图具有较大的迹,表明算法生成的最小刚性图具有较

23、好的刚度代数性能,有利于增强网络稳定性.同时由图8可知MRGAFU算法拓扑链路图权值较小,能较好地延长网络的生命周期.20 30 40 50 60 70 80 90 10005001000150020002500300035004000BxMRGAFUMRG图7刚度矩阵的迹Fig. 7. Trace of rigidity matrix.为较好地验证算法拓扑网络的通信与能耗情况,设置如下的随机场景:在10 m 10 m区域内随机布置36个传感器节点,仿真参考文献8中所给的参数,传输初始能量为0.5 J, Eelect为50 nJ, fs240201-5万方数据物理学报Acta Phys. Si

24、n. Vol. 65, No. 24 (2016) 240201为10 pJ bit m 2,而基站能量通过太阳能供给,不影响网络生命周期,可不考虑基站的能量消耗.分别采用XTC算法与MRGAFU算法进行仿真实验.网络通信链路如图9和图10所示.20 30 40 50 60 70 80 90 100050010001500BWy?MRGAFUMRG图8矩阵的链路权值Fig. 8. The weight of link.B0 2 4 6 8 10012345678910123456789101112131415161718192021222324252627282930313233343536图

25、9 XTC算法网络拓扑结构图Fig. 9. The network topology structure of XTC.0 2 4 6 8 10012345678910123456789101112131415161718192021222324252627282930313233343536图10 MRGAFU算法网络拓扑结构图Fig. 10. The network topology structure of MRGAFU.由图9可以看出,采用XTC算法拓扑优化后,网络中5, 6, 18, 35, 36等节点都仅有一条链路与其相连,而图10中MRGAFU算法每个节点至少有两条链路相连,具有

26、2-连通特性.连通性不同,会影响网络负载的均衡性.计算网络中1, 11, 27, 36四个传感器节点能量随数据包发送个数的变化情况.0 50 100 150 200 250 300 35000.10.20.30.40.50.6JBx_E1E11E27E36图11 XTC算法节点剩余能量Fig. 11. Node residual energy of XTC.JBx_0 50 100 150 200 250 300 35000.10.20.30.40.50.6E1E11E27E36图12 (网刊彩色)MRGAFU算法节点剩余能量Fig. 12. (color online) Node resid

27、ual energy of MRGAFU.由图11与图12比较可知,相同场景下,采用MRGAFU算法,网络中各节点的能量消耗更加均衡,有利于延长网络的生命周期.记录随机场景下网络运行时随循环数增加网络中存活节点数的变化,如图13所示.由图13可知,采用MRGAFU算法拓扑优化后,随着网络的运行,网络中开始出现传感器节点死亡现象的时间要晚于XTC算法的结果,网络中因节点死亡而对网络整体性能开始出现影响的时间要更晚,网络通信传输更加稳定.同时由图中斜率比较可知,采用MRGAFU算法后网络负载更加均衡.240201-6万方数据物理学报Acta Phys. Sin. Vol. 65, No. 24 (

28、2016) 240201对无线传感器网络,分簇是常见的拓扑结构场景,对于大规模分簇网络,直接将头节点信息传输给汇聚节点,会加速头节点能量消耗,如果采用本文算法对于簇头节点间通信进行优化,将有利于提高网络的负载均衡性.0 500 1000 15000510152025303540p3BXTCMRGAFU图13 (网刊彩色)随机场景下网络中的存活节点数Fig. 13. (color online) Survival number of nodes in anetwork.分簇场景设置如下,在160m 160 m范围内随机部署120个节点,仿真中假定无线传感器节点传输范围不限,传输初始能量为0.5

29、J, Eelect为50 nJ,fs为10 pJ bit m 2, mp为0.0013 pJ bit m 4,而基站能量通过太阳能供给,不影响网络生命周期,可不考虑基站的能量消耗.图14和图15为经典低功耗自适应集簇分层型协议(low energy adaptiveclustering hierarchy, LEACH)算法21与经过本文算法优化簇间通信算法MRGAFU的拓扑结构图,图中实心节点表示被选为簇头的头节点,空心节点表示簇内成员节点.图14中, LEACH算法在网络中选择簇头节点,负责聚合与传输网络中成员节点的信息,再将信息直接传递给汇聚节点,算法未对簇与簇之间的通信进行优化.图15

30、中,基于本文算法对簇头节点优化后,在拓扑图中簇头节点至少有两个邻居与其相连,表明簇间通信都是2-连通的,当某条链路受到干扰而中断,不会影响簇间通信的正常进行,簇间通信更加稳定.比较上述两种算法网络中存活节点数目随时间的变化情况,如图16所示.比较两种算法我们发现采用本文算法优化簇间通信后,网络中出现节点死亡现象较晚,表明采用本文算法优化簇间通信有利于加强网络负载的均衡性,以延长网络的寿命.0 20 40 60 80 100 120 140 160020406080100120140160图14 LEACH算法拓扑结构图Fig. 14. The network topology structur

31、e of LEACH.0 20 40 60 80 100 120 140 160020406080100120140160图15 MRGAFU算法拓扑结构图Fig. 15. The network topology structure of MRGAFU.p3B0 200 400 600 800 1000 1200 1400 1600-20020406080100120140LEACHMRGAFU图16 (网刊彩色)分簇场景下网络中的存活节点数Fig. 16. (color online) Survival number of nodes in anetwork.5结论本文基于最小刚性图原理提

32、出了一种新的无线传感器网络拓扑控制算法.该算法综合考虑了240201-7万方数据物理学报Acta Phys. Sin. Vol. 65, No. 24 (2016) 240201生成拓扑链路图中通信链路的权值与生成刚性图的刚度矩阵迹值,既保证了通信链路较短,有利于延长网络的生命周期,同时使生成的通信链路图结构更加稳定,具有较快的收敛速率,网络覆盖定位时具有较小的误差,使网络具有较好的鲁棒性.通过仿真对比验证, MRGAFU算法中通信链路都是2-连通的,生成的刚性图拓扑链路刚度矩阵具有较大的迹值,算法具有较好的连通性及刚度代数特性.参考文献1 El Emary I M M, Al-Gamdi A

33、 H 2014 J. Appl. Med.Sci. 3 52 Li J, Wang F, Li X 2014 J. Networks 9 2443 Xu G, Shen W, Wang X 2014 Sensors 14 169324 Luo X Y, Li S B, Guan X P 2009 IEEE Intelligent Ve-hicles Symposium Xian, China, June 69, 2009 p11985 Dhanapala D C, Jayasumana A P 2014 IEEEACMTrans. Network 22 7846 Bagci H, Korpeo

34、glu I, Yazici A 2015 Parallel and Dis-tributed Systems 26 9147 Wattenhofer R, Zollinger A 2004 Proceedings of the 18thInternational Parallel and Distributed Processing Sym-posium Santa Fe, USA, April 2630, 2004 p2168 Chen Y L 2013 IEEE 7th International Conference onComplex, Intelligent, and Softwar

35、e Intensive SystemsTaichung, China, July 35, 2013 p3359 Qin J, Fu W, Gao H 2016 IEEE Trans. Cybernetics 46110 Song J, Luo Q H, Peng X Y 2014 Acta Phys. Sin. 63128401 (in Chinese) 宋佳,罗清华,彭喜元2014物理学报63 12840111 Hao X C, Liu W J, Xin M J 2015 Acta Phys. Sin. 64080101 (in Chinese) 郝晓辰,刘伟静,辛敏洁2015物理学报64

36、08010112 Fang B, Chen T F 2014 Control Eng. 21 178 (in Chi-nese) 方斌,陈特放2014控制工程21 17813 Luo X Y, Yan Y L, Li S B 2013 Computer Networks 57103714 Shames I, Summers T 2014 Sensor Array and Multi-channel Signal Processing Workshop (SAM) A Coruna,Spain, June 2225, 2014 p2915 Zelazo D, Franchi A, Bltho H

37、 H 2013 Int. J. Robot.Res. 34 10516 Anderson B D O, Shames I, Mao G 2010 SIAM J. Dis-crete Mathematics 24 68417 Shames I, Fidan B, Anderson B D O 2009 Automatica45 105818 Shames I, Summers T H 2015 IEEE Trans. Network Sci.Eng. 2 8419 Hendrickx J M, Anderson B, Blondel V D 2005 44thIEEE Conference on

38、 European Control CDC-ECC05Seville, Spain, December 1215, 2005 p217620 Chen Z J, Ouyang Y L 2012 Computer Eng. 38 10421 Heinzelman W R, Chandrakasan A, Balakrishnan H2000 Proceedings of the 33rd Hawaii International Con-ference on System Sciences Maui, USA, January 47,2000 p10240201-8万方数据物理学报Acta Ph

39、ys. Sin. Vol. 65, No. 24 (2016) 240201Topology optimization algorithm for wireless networksbased on the algebraic properties of minimumrigid graph Luo Xiao-Yuany Li Hao Ma Ju-Hai(School of Electrical Engineering, Yanshan University, Qinhuangdao 066004, China)( Received 14 January 2016; revised manus

40、cript received 23 July 2016 )AbstractFor wireless sensor networks, with energy constrained, topology optimization can reduce energy consumption andimprove the structure of communication link. Based on the minimum rigid graph, a new topology optimization algorithmis presented in this paper, by consid

41、ering the weights of communication links in graph and the generated algebraicproperties of rigid graph. The proposed algorithm not only ensures the communication link is shorter which can prolongthe network life cycle, but also keeps the graph structure more stable, which means that the network has

42、good robustness.It is shown that communication link obtained by the proposed algorithm is shorter than that obtained by the relatedexisting algorithms. As a result, the proposed algorithm has good network connectivity and structure stability. At thesame time the trace of the generated rigid matrix i

43、s very big so that the proposed algorithm has excellent algebraicrigidity properties of a network.Keywords: wireless sensor network, topology optimization, minimally rigid graph, algebra propertyPACS: 02.10.Ox, 02.10.Yn, 02.10.v DOI: 10.7498/aps.65.240201* Project supported by the National Natural Science Foundation of China (Grant No. 61375105). Corresponding author. E-mail: 240201-9万方数据