应用Delaunay图的拓扑控制

应用Delaunay图的拓扑控制 Computer Engineering and Applications计算机工程与应用 2010，46(5) 105 应用 Delaunay图的拓扑控制张作锋，刘三阳，冯海林 ZHANG Zuo-feng，LIU San-yang，FENG Hai—lin 西安电子科技大学理学院，西安 710071 School of Science，Xidian University，Xi’an 710071，China E—mail：zfzhangxd@gmail．tom ZHANG Zuo-f...

Computer Engineering and Applications计算机工程与应用 2010，46(5) 105 应用 Delaunay图的拓扑控制张作锋，刘三阳，冯海林 ZHANG Zuo-feng，LIU San-yang，FENG Hai—lin 西安电子科技大学理学院，西安 710071 School of Science，Xidian University，Xi’an 710071，China E—mail：zfzhangxd@gmail．tom ZHANG Zuo-feng．LIU San-yang。FENG Hai-lin。Applying Delaunay graph to topology contro1．Computer Engineering and Applications，2010。46(5)：105-107． Abstract：The main design purpose of topology control of Wireless Sensor Networks(WSN)is to reduce node power consumption and prolong the lifetime of WSN．However，the energy consumption of WSN comes from communication module mostly．By slowing down energy consumption of wireless communication module，controlling the neighbor set of each node，reducing the communica- tion links and restricting the communication in the crucial links，node power consumption can be reduced．Combining the MG model with the Delaunay graph，this paper presents a topology control algorithm MEDel by restricting the communication links and preserving the optimal energy consumption path in Delaunay graph．This algorithm has the advantages of strong connected- ness，symmetry and bounded average node degree． Key word s：wireless sensor networks；topology control algorithm；MG model；Delaunay graph；MEDel algorithm 摘要：无线传感器网络拓扑控制的主要任务是减少节点的能量消耗，从而延长整个网络的生存时间。而无线传感器网络的能量消耗主要集中在无线通信模块上，因此，通过降低无线通信模块的能量消耗和控制邻居节点集，减少通信链路，把通信限制在重要链路中，可以减少节点的能量消耗。基于以上因素，将 MG模型与 Delaunay图结合，在 Delaunay图中限制通信链路并保留最优能耗路，得到 MEDel算法。该算法具有强连通性、对称性和平均度有界的优点。关键词：无线传感器网络；拓扑控制算法；MG模型；Delaunay图；MEDel算法 DOI：10．3778／j．issn．1002—8331．2010．05．031 文章编号：1002—8331(2010)05—0105—03 文献标识码：A 中图分类号：TP393 1 引言拓扑控制的思想是限制给定节点的邻节点数目。在密集型的网络中，一个节点有许多邻节点，如果发射功率足够大，就能实现它们之间的直接通信。但高发射功率会消耗大量的能量，而且邻节点数过多会降低路由协议和MAC协议的效率，邻节点数过少，则会降低网络的可靠性并造成部分节点间的通信需要选择能量消耗较大的多跳通信链路，从而使得网络能量消耗不平衡。目前，大多数研究假设节点是同构的(homogenous net)。在功率控制研究中，一般认为网络中的所有节点都具有相同的最大发射功率(基于UDG(Unit Disk Graph)模型)，然而事实上，即使网络中所有的传感器节点使用相同的发射功率，由于天线质量、地形、环境等多方面的差异，各个节点所形成的发射范围也是各不相同的，且研究人员已经发现这种差别很大lll。考虑到以上因素，选择更一般的MG(Mutual inclusion Graph)模型。 UDG模型为：两个节点可以通信，如果它们的 Euclidean距离不大于一个阈值。很多文献将 UDG模型与 Delaunay图结合，可得到UDel图。该图具有很多良好的性质。MG模型为：两个节点可以相互通信，只有当它们位于彼此的发射范围内，即节点“，之间的Euclidean距离满足 ll ll~ 题嘲，简称RA(Range As— signment)问题。典型的功率控制算法有 COMPOWt41，LMA和 LMNtS，CBTC算法，XTC算法[7】和邻近图算法等。典型的分簇算法有 GAF算法[81、TopDisc算法[91、HEED算法[1oJ等。经典的邻近图算法有 DRNG、DLMS3~11、G 、YG 等。其中 DRNG，DLMST 算法邻节点数过少，而 COMPOW、CBTC、GAF、TopDisc、HEED 等算法又不适用于 heterogeneOUS net。考虑到以上因素，在 Dclaunay图上保留了无线通信消耗最小的边即保留最优能耗路并首次与MG结合，提出了更符合实际应用的基于邻近图的MEDel算法，该算法具有良好的拓扑性基金项目：国家自然科学基金(the National Natural Science Foundation of China under Grant No．60674108 o 作者简介：张作锋(1982一)，男，硕士研究生，主要研究方向为无线传感器网络；刘三阳(1959一)，男，教授，博士生导师，主要研究方向为最优化计算方法，网络优化，无线传感器网络等；冯海林(1966一)，女，副教授，主要研究方向为优化理论与应用，网络优化算法等。收稿日期：2008—09—18 修回日期：2008—11-26 106 2010，46(5) Computer Engineering and Applications计算机工程与应用质，如强连通性，对称性，平均度有界等。设 dist(a，b)>dist(a，c)；dist(a，b)>dist(b，c)。因为能量消 2 相关知识 2．1 Voronoi图定义任意两点P和g之间的欧氏距离，记作dist(p，g)。对于二维平面有 r—————— —— ———————— —— 一 dist(p，q)=、／(p 一q )。+(p厂q )。设 {P ，P ，⋯，p }为平面上任意n个互异的点；这些点也就是基点。所谓 P对应的 Voronoi图 41，就是平面的一个子区域划分。整个平面因此被划分为个单元，它们具有如下性质：任一点q位于点P 所对应的单元中，当且仅当对于任何的P／∈P， J≠i，莉唷 dist(q，p。)dist(a，c)“+dist(b，c)”，则删除边；否则保留边。因此三角形中的任意两点间的最优能耗路可保留，对 De— launay图中的所有三角形进行准则的判断，则最优能耗路可以保留下来。经删除边得到的Delaunay图记为EDel。 3．2 MEDel算法步骤对于 n个节点的无线传感器网络有(假设MG强连通) 步骤 1求出n个节点的 Delaunay图；步骤 2由 3．1节中的准则求出EDel图；步骤 3令 EDel =MGnEDel；步骤4如果EDel 不连通，则将EDel 中的不连通分支用 MG中对应的最短边连接，得到MEISel图；若EDel 连通，则其即为 MEDel图。 4 算法分析与仿真 4．1 算法特性分析 4．1．1 MEDel图平均度有界引理_l4]若 n≥3则在与平面上任意 n个基点相对应的 Voronoi图中，边的数目不会超过 3n一6。定理 Delaunay三角剖分的平均度小于 6。证明由Delaunay三角剖分的定义知，Delaunay图中的边与 Voronoi图中的边一一对应，由引理知 Delaunay图的边数也不会超过 3n一6。由平均度的定义有Delaunay图的平均度、：垒 <—2x(3 — n-6)：6 ～ <6 n n 其中m为Delaunay图的边数。证毕。 MEDel算法经过步骤 2，步骤3，图的平均度只能降低，而步骤4只需将不连通分支加边变为连通图，因此平均度数也不会超过 6。 4．1．2 强连通性(对称性) 由于步骤 3求的是交集，而 MG是强连通的(对称的)，步骤4确保了MEDel算法的连通性(对称性)，如果不连通，则添加的是MG中的边，因此MEDel算法是强连通的(对称的)。 4．2 算法仿真图(与UDel，DRNG比较) 仿真参数设置：节点：5O个，目标区域：100 m~100 nl，最大传输半径：R~=35 m，每个节点的传输范围：28—35 m，MEDel算法中n=3。由图3知，MEDel算法和DRNG算法都使得网络拓扑图中边的数量明显减少，降低了节点的发射功率，同时减少了节点间的通信干扰。尽管 MEDel图中的边多于DRNG图中的边，由3．1节中的规则知，这些边是能量最优的，它们的存在可以减少部分节点的能量消耗。避免了选择较大能量消耗的多跳路径。DLMST比DRNG图中的边数更 n】，由分析和仿真结果知 MEDel算法在节省能量和网络的可靠性方面优于 DRNG算法和 DLMST算法，且可均衡能量消耗。它们都适用于hetero— geneous ／leto 4．3 算法节点度仿真图图4中坐标对应节点数，Y坐标对应度数值。dmin为最小度数，dmax为最大度数，davg为平均度数。由仿真图知，随着节点数目的增多，节点的平均度数增加缓慢，且趋于平缓，节点的最大度数维持在 6左右。张作锋，刘三阳，冯海林：应用 Delaunay图的拓扑控制 2010，46(5) 107 MG图 MEDel图 DRNG图(with edge remova1) 图3 算法仿真结果图节点数图4 节点度仿真图 5 结束语考虑到邻近图在拓扑控制算法中的应用和 Delaunay图的良好性质，应用无线通信的能量消耗关系式剔除Delaunay图中能量消耗较大的边，保留了能量最优路径，并首次将 Delaunay 图和MG模型结合，从而使得网络拓扑更加符合实际。通过对 MEDel算法的仿真，得到了良好的效果。参考文献： [1】Li X Y，Song W z，Wang Y．Localized topology control for hetero— geneous wireless sensor networks口1．ACM Trans on Sensor Netwo~s， 2005，2(1)：129—153． [2]孙利民．无线传感器网络[M] E京：清华大学出版社，2005．『3]3 Kirousis L M，Kranakis E，Krizanc D，et a1．Power consumption in packet radio networks[J1_Theoretical Computer Science，2000，243 (1／2)：289—305．『4】Narayanaswamy S，Kawa~a V，Sreenivas R S，et a1．Power control in ad—hoc networks：Th eory，architecture，algorithm and implementation of the COMPOW protocol[C]／／Proc of the European Wireless Conf Florence．2o02：156-162．【5]5 Kubisch M，Karl H，Wolisz A，et a1．Distributed algorithms for trans— mission power control in wireless sensor networks[C]／／Yanikomeroglu H．Proc of the IEEE Wireless Communications and Networking Conf (WCNC)．New York：IEEE Press，2003：16—20．【6】Li L，Halpern J Y，Babl P，et a1．A cone—based distributed topology control algorithm for wireless multi-hop networks[J]．IEEE／ACM Trans on Networking，2005，13(1)：147—159．『7]7 Wattenhofer R，Zollinger A．XTC：A practical topology control algo— rithm for ad—hoe networks[C]／／Panda D K，Duato J，Stunkel C．Proc of the Int’l Parallel and Distributed Processing Symp(IPDPS)．New Mexico：IEEE Press，2004：216—223． [8】8 Xu Y，Heidemann J，Estrin D．Geography informed energy eonserva- tion for ad hoc routing[C]／／Prec of the 7th Annual International Conference on Mobile Computing and Networking，2001：70—84． [9】Deb B，Bhatnagar S，Nath B．A topology discovery algorithm for sensor networks witll applications to network management．DCSTR- 441[R1．Rutgers University，2001． [10]Younis O，Fahmy S．HEED：A hybrid，energy—efficient，distributed clustering approach for ad hoc sensor networks[J]．IEEE Trans on Mobile Computing，2004，3(4)：660—669．【1 l】Li N，Hou J C．Topology control in heterogeneous wireless networks： Problems and solutions[C]／／Proc of the IEEE Conf on Computer Communications(INFOCOM)．New Y0rk：IEEE Press，2004：232-243． [12]Gabriel K，Sokal R．A new statistical approach to geographic vail— ation analysis[J]．Systematic Zoology，1969，18：259-278．【13】Yao A C C．On constructing minimum spanning trees in k—di- mensional spaces and related problems[J]．SIAM Journal on Com— puting，1982，11：721-736．【14]de Berg M，van Kreveld M．计算几何一算法与应用【M】．邓俊辉，译I2版．北京：清华大学出版社，2005：165—214． (上接 88页) 盲水印检测算法却可以很容易地检测水印的存在。这充分说明文中所提出的盲水印检测器有很好检测水印的性能。 6 结束语先对Wavelet变换高频子带的系数进行数学模型统计分析，得出了Wavelet变换的高频子带系数符合广义高斯分布重要结论，然后介绍了乘性水印的优点并给出了乘性嵌入规则。因为Wavelet变换的高频子带系数符合广义高斯分布，提出了一种在Wavelet变换的高频子带乘嵌入水印规则与盲检测算法框架，并进行了多种攻击实验。实验结果表明在 Wavelet变换域所提出水印检测器具备了良好的检测水印的性能。参考文献：【1]朱香卫，肖亮，吴慧中．基于视觉显著性和置乱技术的小波域鲁棒性水印算法们．通信技术，2008，41(196)：50—52．【2]靳济芳．Visual c++小波变换技术与工程实践【M】．北京：人民邮电出版社，2004：1-115． [3]Clarke R J．Transform coding of ima ges[M]．UK：Academic Press， 1985：19—31，87—90． f4】Cheng Q，Huang T S．Robust optimum detection of transform do- main muhiplieative watermarks[J]．IEEE Trans on Signal Processing， 2003，51(4)：906—924．【5】Papoulis A S，Pillai U．Probability，random variables，and stochastic processes[M]．B t0n：McGraw—Hil1．2002．【6】Barni M，Bartolini F，De Rose A，et a1．A new decoder for tlle opti— mum recovery of non-additive watermarks[J】．IEEE Trans on Image Processing，2001，10(5)：755—765． [7】Cheng Q，Huang T S．Robust optimum detection of transform do- main muhiplicative watermarks[J]．IEEE Trans on Signal Processing， 2003，51(4)：906—924． [8】李建良，蒋勇，汪光先．计算机数值方法【M】．南京：东南大学出版社， 2O0o．籁

                    本文档为【应用Delaunay图的拓扑控制】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

应用Delaunay图的拓扑控制

你可能还喜欢