用户名: 密码: 验证码:
无线自组网中可自维护的拓扑控制算法研究
详细信息    本馆镜像全文|  推荐本文 |  |   获取CNKI官网全文
摘要
无线自组网的拓扑对网络性能有很大的影响,密度高的拓扑会因干扰的加大而降低容量,稀疏的拓扑又会因为链路失效和网络分割而导致网络不连通。拓扑控制的目的就是优化网络的性能,同时减少节点的能量消耗。由于无线自组网的拓扑是动态变化的,故要求拓扑控制算法不仅能在初始时建立具有某种性质的网络拓扑结构,而且在拓扑发生变化后,算法能够重构网络,保障网络的连通性,并且以较小的开销维护网络已有的属性。
     本文主要分析了现有的拓扑控制算法存在的两个问题:维护周期固定不变和未考虑环境变化的因素。针对这两个问题分别提出了维护周期自适应变化的拓扑控制算法VPLMA(Varying Periods Local MeanAlgorithm)和自适应环境变化的拓扑控制算法EATCA(EnvironmentAdaptive Topology Control Algorithm)。VPLMA算法是对LMA算法进行改进,采用动态变化的维护周期的方法来维护网络的拓扑结构保持其连通性。EATCA算法是通过预测节点周围环境的变化,自适应调整节点的发射功率以保证网络拓扑的稳定,从而保证网络的性能不受影响。
     最后通过仿真实验验证了本文提出的算法的有效性。仿真结果表明采用维护周期自适应变化的拓扑控制算法VPLMA,能保证在数据发送成功率和端到端延迟基本不变的情况下,使能量消耗减少10%左右。采用自适应环境变化的拓扑控制算法EATCA能降低30%左右的端到端的延迟,提高10%左右数据发送成功率。
The topology of wireless ad hoc network has a significant impact on its performance in that a dense topology may induce high interference and low capacity, while a sparse topology may induce link failure and network partitioning. Topology control aims to maintain a topology that optimizes network performance while minimizing energy consumption. Owing to the topology of the wireless ad hoc network is dynamic, the topology control algorithm not only should establish a network topology which has some characters in the initial time, but also can reconstruct the network topology when it changed. This is important for the wireless network to ensure connectivity and the existing properties in low cost.
     This thesis analyze two problems of the present topology control algorithms. Considering the two problems, this thesis proposes two algorithms, named VPLMA and EATCA. The VPLMA algorithm is designed based on LMA algorithm, and it maintains network topology by alterable period.In EATCA algorithm, network nodes can predict the environmental change, then it adjusts transmitting power to ensure the stability of network topology, thus ensuring network performance.
     Finally, this thesis verify the effectiveness of the two algorithms through simulation. The results show that the VPLMA algorithm can reduce energy consumption by 10%, while it guarantees packet delivery ratio and end to end delay unchanged. And the EATCA algorithm can reduce end-to-end delay by 30% and increase packet delivery ratio by 10%.
引文
[1]David AB.Accomplishments of the DARPA Survivable Adaptive Networks SURAN Program[C].In Proceedings of the IEEE MILCOM Conference,1990.
    [2]Barry ML,Robert R,Ambatipudi RS.Goals and Challenges of the DARPA GloMo Program[J].IEEE Personal Communications,1996,3(6):34-43.
    [3]Liu G,Li ZG,Zhou XS.Transmission power control for wireless sensor networks[C].International Conference on Wireless Communications,Networking and Mobile Computing,WiCOM,2007:2596-2599.
    [4]Santi P.Topology Control in Wireless Ad Hoc and Sensor Networks[J].ACM Computing Surveys,2005,37(2):164-194.
    [5]张禄林,张宁,赵亚男,等.多跳无线网网络拓扑控制优化目标研究[J].通信学报,2005,3(26):117-123.
    [6]Chlamtac L,Conti M,Liu J.Mobile ad hoc networking:imperatives challenges,Ad Hoc Networks[J],2003,1(1):1364.
    [7]Mobile ad hoc networking(MANET):Routing Protocol Performance issues and evaluation considerations[EB/OL].IETF RFC 2501,1999,Available:http://www.ieft.org/rfc/rfc2501.txt.
    [8]Li J,Blake C,Decouto DSJ.Capacity of ad hoc wireless networks[C].Mobile Computing and Networking,2001,61-69.
    [9]Recent improvements on Bluetooth[EB/OL].http://www.bluetooth.org/
    [10]Chen ZD,Kung HT,Vlah D.Ad Hoc Relay Wireless Networks over Moving Vehicles on Highways[C].Proceedings of the 2001 ACM International Symposium on Mobile Ad Hoc Networking and Computing:MobiHoc 2001,2001,247-250.
    [11]George N,Rahim T.On the Relaying capability of Next-Generation GSM Cellular Networks[J].IEEE Personal Commun Mag,2001,1(8):40-47.
    [12]Ljubica B,Levente B,Srdjan C.Self-organization in mobile Ad hoc network:the approach of terminodes[J].IEEE Communication Magazine,2001,39(6):166-174.
    [13]Goldsmith AJ.Design Challenges for Energy-Constrained Ad Hoc Wireless Networks[J].IEEE Wireless Communications,2002,9(4):8-27.
    [14]孙宝林,李腊元.多跳无线移动Ad Hoc网络路由协议的研究分析[J].小型微型计算机系统,2004,25(10):1731-1741.
    [15]李云,赵为粮,隆克平,等.无线Ad Hoc网络支持QoS的研究进展与展望[J].软件学报,2004,12(15):1885-1893.
    [16]NS manual[EB/OL],http://www.ecse.rpi.edu/Homepages/shivkuma/teaching/fall/ns-2/ns_doc.pdf,2005.
    [17]Cheng X,Narahari B,Simha R.Strong minimum energy topology in wireless sensor networks:NP-Completeness and heuristics[J].IEEE Transactions on Mobile Computing,2003,3(2):248-256.
    [18]Kawadia V,Kumar PR.Principles and protocols for Power Control in Wireless Ad Hoc Networks[J],IEEE JSAC,2005,23(1):76-88.
    [19]Yu CS,Shin KG,Lee B.Power-Stepped protocol:Enhancing spatial utilization in a clustered mobile ad hoe network[J].IEEE Journal on Selected areas in communications,2004,22(7):1322-1334.
    [20]Rover EM,Smith PM,Moser LE.An analysis of the optimum node density for Ad hoe mobile networks[C].Proceedings of the IEEE International Conference on Communications,2001.
    [21]Sanchez M,Manzoni P,Haas ZJ.Determination of critical transmission range in Ad hoc networks[C].Proceeding of the Multiaccess,Mobility and Teletrafic for Wireless Communcations,2000.
    [22]Ramanathan R,Rosales HR.Topology control of multihop wireless networks using transmit power adjustment[C].Proceedings of the IEEE INFOCOM,2001:404-413.
    [23]Narayanaswamy S,Kawadia V,Sreenivas RS.Power Control in Ad Hoc Networks:Theory,Architecture,Algorithm and Implementation of the COMPOW Protocol[C].Proceedings of the European Wireless Conference-Next Generation Wireless Networks:Technologies,Protocols,Services and Applications,2002,156-162.
    [24]Elbat TA,Krishnamurthy SV.Power management for throughput enhancement in wireless Ad hoc networks[C].IEEE International Conference on Communications,2000,3:1506-1513.
    [25]Shen Y,Cai YZ,Xu XM.A Shortest-Path-Based Topology Control Algorithm in Wireless Multihop Networks[J].ACM SIGCOMM Computer Communication Review,2007,37(5):29-38.
    [26]Lloyd EL,Liu R,Marathe MV.Algorithmic aspects of topology control problems for ad hoc networks[C].Proceedings of the 2002 ACM International Symposium on Mobile Ad Hoc Networking and Computing:MobiHoc 2002,2002:123-134.
    [27]Santi P,Blough DM.The Critical Transmiting Range for Connectivity in Sparse Wireless Ad Hoe Networks[J].IEEE Transition on Mobile Computing,2003,2(1):25-39.
    [28]Li H,Yu D.A statistical study of neighbor node properties in ad hoc network[C].Proceeding of International Conference on Parallel Processing Workshops,2002:103-108.
    [29]Dousse O,Thiran P,Hasler M.Connectivity in ad hoc and hybrid networks[C].IEEE INFOCOM,2002:1079-1088.
    [30]Betstetten C.On the connectivity of wireless multihop networks with homogeneous and inhomogeneous range assignment[C].Proceeding of IEEE Vehicular Technology Conference,2002:1706-1710.
    [31]Ramasubramanian V,Mosse D.Statistical analysis of connectivity in unidirectional ad hoc networks[C].Proceeding of the International Conference on Parallel Processing Workshops,2002:109-115.
    [32]Desai M,Maniunath D.On the connectivity in Finite ad hoc networks[J].IEEE Communications Leters,2002,6(10):437-439.
    [33]Yu D and Li H.On the definition of ad hoc network connectivity[C].Proceeding of International Conference on Communication Technology,2003:990-994.
    [34]Toussaint G.The relative neighborhood graph of a finite planar set[J].Pattern Recognition,1980,12(4):261-268.
    [35]Gabriel KR,Sokal RR.A new statistical approach to geographic variation analysis[J].Systematic Zoology,1969,18(3):259-278.
    [36]Yao AC.On constructing minimum spanning trees in k-dimensional spaces and related problems[J].SIAM Journal of Computing,1982,11(4):721-736.
    [37]Bose P,Gudmundsson J,Smid M.Constructing plane spanners of bounded degree and low weight[C].In:Raman R,ed.Proc.of the 10th Annual European Symp.of Algorithms.London:Springer-Verlag,2002.:234-246.
    [38]Shen CC,Srisathapornphat C,Liu R.CLTC:a cluster-based topology control framework for ad hoc networks[J].IEEE Transition on Mobile Computing.2004,3(1):18-32.
    [39]邹仕洪,程时端.一种多速率移动自组网中的拓扑控制算法[J].软件学报,2004,12(15):1869-1876.
    [40]沈中,常义林,崔灿,等.一种基于最短路径树的无线Ad hoc网络拓扑维 护算法[J].电子与信息学报,2007,2(29):323-327.
    [41]王炫,李建东,张文柱.拓扑控制对Ad Hoc网络性能的影响[J].计算机科学,2006,6(33):44-47.
    [42]罗玉宏,王建新,黄家玮,等.移动自组网基于能量效率的分布式拓扑控制算法[J].软件学报,2007,18(3):702-713.
    [43]赵林亮,姜月秋,初春,等.移动Ad hoc网络中基于MIB的分簇拓扑控制算法的研究[J].小型微型计算机系统,2005,11(26):1881-1885.
    [44]沈中,常义林,崔灿,等.一种建立可自维护且具有最小能量特性的无线网络的分布式拓扑控制算法[J].计算机学报,2007,4(30):569-578.
    [45]仲英济,袁东风.基于位置信息的无线小区自组织网络拓扑控制研究[J].电子与信息学报,2007,3(29):707-710.
    [46]仲英济,袁东风.基于拓扑控制的无线自组织网络TCP性能改进研究[J].通信学报,2006,7(27):46-52.
    [47]Li N,Hou JC,Sha L.Design and analysis of an MST based topology control algorithm[C].IEEE INFOCOM,2003:1702-1712.
    [48]Rodoplu V,Meng TH.Minimum energy mobile wireless networks[J].IEEE Journal on Selected Areas in Communications,1999,8(17):1333-1344.
    [49]Li L,Halpern JY,Bahl V.Analysis of a cone-based distributed topology control algorithms for wireless multi-hop networks[C].Proceeding ACM Symposium on Principle of Distributed Computing(PODC),2001:264-273.
    [50]Li L,Halpern J,Bahl P.A cone-based distributed topology-control algorithm for wireless multi-hop networks[J].IEEE/ACM Trans.on Networking,2005,13(1):147-159.
    [51]Liu J,Li B.Distributed topology control in wireless sensor networks with asymmetric links[C].IEEE GLOBECOM,2003:1257-1262.
    [52]Anastasi G,Conti M,Falchi A.Performance Measurements of Mote Sensor Networks[C].MSWIM '04,2004:29-31.
    [53]Liang B,Dong M.Balancing distance and lifetime in delay constrained ad hoc networks[C].MobiHoc,2006.97-107.
    [54]Berkeley.TinyOS project[EB/OL],http://webs.cs.berkeley.edu/tos/.
    [55]Rai V,Mahapatra RN.Lifetime modeling of a sensor network[C].In Proceedings of Design,Automation and Test in Europe(DATE '05),Munich,Germany,2005,(1):202-203.
    [56]徐雷鸣,庞博,赵耀.NS与网络模拟[M].人民邮电出版社,2003.
    [57]吴震东,李善平.传感器网络中一种基于链路稳定性和多路径的拓扑控制算法.计算机研究与发展[J],2007,44(2):216-222.
    [58]Charney G,Fjortoft R,Neumann JV.Numerical integration of the barotropic vorticity equation[J],1950,2:237-254.
    [59]丑纪范,徐明.短期气候数值预测的进展和前景[J].科学通报,2001,46(11):890-895.
    [60]Kim JM,Jang W.AODV based energy efficient routing protocol for maximum lifetime in MANET[C].Proceedings of the Advanced International Conference on Telecommunications and International Conference on Internet and Web Applications and Services,2006.
    [61]雷涛,郝福珍,鄢楚平.一种改进的无线自组网QoS路由协议-EQAODV[J].计算机应用,2006,26(6):1284-1291.
    [62]Kubisch M,Karl H,Wolisz A.Distributed algorithms for transmission power control in wireless sensor networks[C].IEEE WCNC,2003.
    [63]Gabriel KR,Sokal RR.A new statistical approach to geographic variation analysis[J].Systematic Zoology,1969,18(3):259-278.
    [64]Toussaint G.The relative neighborhood graph of a finite planar set[J].Pattern Recognition,1980,12(4):261-268.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700