中文模板

Size: px

Start display at page:

Download "中文模板"

魄岁赫舍里
5 years ago
Views:

1 ISSN CODEN RUXUEW Journal of Software Vol18 No4 April 2007 pp DOI: /jos Tel/Fax: by Journal of Software All rights reserved ( ) ) 2 ( ) 3 ( ) Topology Control for Wireless Sensor Networks ZHANG Xue 123+ LU Sang-Lu 12 CHEN Gui-Hai 12 CHEN Dao-Xu 12 XIE Li 12 1 (State Key Laboratory for Novel Software Technology (Nanjing University) Nanjing China) 2 (Department of Computer Science and Technology Nanjing University Nanjing China) 3 (Department of Electrical Engineering School of Engineering Nanjing Agricultural University Nanjing China) + Corresponding author: Phn: Fax: zhangxue@dislabnjueducn Zhang X Lu SL Chen GH Chen DX Xie L Topology control for wireless sensor networks Journal of Software (4): Abstract: Topology control is one of the most fundamental problems in wireless sensor networks It is of great importance for prolonging network lifetime reducing radio interference increasing the efficiency of MAC (media access control) protocols and routing protocols among other things This paper makes a full-scale introduction to the advancement of research on topology control Firstly the topology control problem and the design objectives are clearly presented Secondly an introduction is made to representative research efforts along with analyses and comparisons in two aspects power control and sleep scheduling respectively At the same time the defects of those efforts are clearly pointed out Finally existing problems open issues and research trends are analyzed and summarized Key words: : sensor network; wireless network; topology control; power control; sleep scheduling MAC(media access control) : ; ; ; ; Supported by the National Natural Science Foundation of China under Grant No ( ); the National High-Tech Research and Development Plan of China under Grant No2006AA01Z199 ( (863)); the National Grand Fundamental Research 973 Program of China under Grant No2006CB ( (973)); the Natural Science Foundation of Jiangsu Province of China under Grant NoBK ( ) Received ; Accepted

2 944 Journal of Software Vol18 No4 April 2007 : TP393 : A ACM TOSN(transactions on sensor networks) [1] : ; ; MAC(media access control) ; [2] ; ( ) ( ) 4 [2] : (1) : (2) : (mobile ad hoc network MANET) (3) : (4) : XTCCCPSPAN HEED : (1) : [3] (barrier coverage) [4] ( ) ; ;

3 : 945 k k- k 1-1- k- 1 Voronoi (2) : k k- k (1- ) 1 (3) : [5] [6] (4) : λbits/s 16AW 1 λ bits/s 2 π L nr A W π 0 L n r (5) : MAC 1 ( ) r [8] r (6) : ; [9] : ; (7) : ( ) (spanner property) [10] 2 1 [7] :

4 946 Journal of Software Vol18 No4 April 2007 Algorithms Table 1 Comparison of topology control algorithms for wireless sensor networks Connectivity 1 Synchronization required Based on location or direction Complexity Node density Network scale Heterogeneity COMPOW Yes No No Medium Sparse Medium No CLUSTERPOW Yes No No High Sparse Medium No LMA No No No Low Sparse Large Possible LMN No No No Low Sparse Large Possible CBTC Yes No Yes Low Sparse Large No DRNG Yes No Yes Medium Sparse Large Possible DLMST Yes No Yes Medium Sparse Large Possible XTC Yes No No Low Sparse Large Possible RIS No Yes No Low Dense Large Possible MSNL No No Yes Medium Dense Large No LDAS No No No Medium Dense Large No ASCENT No No No Low Dense Large Possible PEAS No No No Low Dense Large Possible PECAS No No No Medium Dense Large Possible CCP Yes No Yes High Dense Large No SPAN Yes No No Medium Dense Large Possible LEACH Yes No Medium Dense Small No EECS Yes No Medium Dense Small No LDS No Yes Medium Dense Small No GAF Yes No Yes Medium Dense Large No GBR Yes No Yes High Dense Large No TopDisc Yes No No High Dense Medium No HEED No Yes No High Dense Large No 21 (University of Patras) Kirousis [11] RA(range assignment) N={u 1 u n } d(d=123) r(u i ) u i RA ( ) N ( r( ui )) α α 2 RA O(n 4 ) ; [12] [11] RA NP RA (1) Narayanaswamy COMPOW [8] : COMPOW P i P i HELLO COMPOW Pcom RT RT P u i P com max RT Pi P max P com COMPOW Kawadia Kumar CLUSTERPOW [13] COMPOW d CLUSERPOW d RT Pmin P com CLUSTERPOW CLUSTERPOW P min

5 : 947 (2) Kubisch LMA LMN [14] : (3) Wattenhofer Li CBTC [15] : u p uρ u ρ ρ 5π/6 Bahramgiri CBTC [16] (4) Li Hou DRNG DLMST [17] : G G RNG(relative neighborhood graph)gg(gabriel graph)dg(delaunay graph)yg(yao graph) MST(minimum spanning tree) DRNG RNG DLMST MST DRNG DLMST Wattenhofer XTC [18] XTC : : Kumar RIS [19] RIS RIS Berman MSNL [20] MSNL 3 : MSNL Wu LDAS [6] Wu LDAS LDAS Cerpa Estrin ASCENT [21] ;

6 948 Journal of Software Vol18 No4 April 2007 ASCENT ASCENT Ye PEAS [22] PEAS 3 : PEAS Gui PECAS [23] PEAS PEAS PECAS Xing CCP [24] Chen SPAN [25] CCP SPAN : ( ) Heinzelman LEACH [26] LEACH Ye EECS [27] EECS LEACH (Syracuse University) Deng LDS [5] LDS LDS Deng LDS [28] Xu GAF [29] GAF 3 : GAF GAF Zhang GBR [30] GAF GBR (Rutgers University) Deb TopDisc [31] [32] [33] NP [32] NP [32] k NP [34] TopDisc Younis Fahmy HEED [35] HEED 34 3 XTC [18] CCP [24] SPAN [25] HEED [35]

7 : XTC XTC RNG XTC 3 : (1) : u p p w v w p v u p u u (2) : u p p u (3) : u u v u w w p u v p u u v XTC XTC XTC XTC 32 CCP CCP : k- k- CCP ( ): 2 k- k- CCP k- CCP k- Xing A k- :(1) ;(2) k- ;(3) k- Xing k- O(N 3 ) N 2 CCP 3 : CCP CCP HELLO WITHDRAW ; WITHDRAW HELLO ; HELLOWITHDRAW JOIN JOIN ; JOIN CCP CCP 2 CCP Xing CCP SPAN SPAN 33 SPAN SPAN : ; : ( ) u u

8 950 Journal of Software Vol18 No4 April 2007 : SPAN ( ) ; SPAN delay: E r N delay = + U i + R N i T 1 E (1 ) i m U i = Ci 2 E r E m ( )U i i R [01] N i i T C i i SPAN SPAN SPAN SPAN : 34 HEED HEED : HEED (AMRP) AMRP Younis Fahmy AMRP ( ) HEED O(1) ; AMRP; CH p : CH E max C p E r p = pmin m C p ( 5%) ;E r ;E m ;p min ; CH p 2 CH p CH p 1 HEED HEED 4 ( ) : (1)

9 : 951 [36] [37] [37] [37] (2)? (3) [38] CCP [4] (4) [39] ( )? MAC MAC

10 952 Journal of Software Vol18 No4 April 2007 [40] (5) LEACHHEED 5 CLUSTERPOW LMA CBTC DRNG XTC CCPSPANRIS HEEDGAFTopDisc References: [1] Akyildiz IF Su W Sankarasubramaniam Y Cayirci E A survey on sensor networks IEEE Communications Magazine (8): [2] Poduri S Pattem S Krishnamachari B Sukhatme G A unifying framework for tunable topology control in sensor networks Technical Report CRES University of Southern California [3] Meguerdichian S Koushanfar F Potkonjak M Srivastava MB Coverage problems in wireless ad-hoc sensor networks In: Bauer F Cavendish D eds Proc of the IEEE Conf on Computer Communications (INFOCOM) New York: IEEE Press [4] Thai MT Wang F Du DZ Coverage problems in wireless sensor networks: designs and analysis Int l Journal of Sensor Networks (Special Issue on Coverage Problems in Sensor Networks) [5] Deng J Han YS Heinzelman WB Varshney PK Scheduling sleeping nodes in high density cluster-based sensor networks ACM/Kluwer Mobile Networks and Applications (MONET) (6): [6] Wu K Gao Y Li F Xiao Y Lightweight deployment-aware scheduling for wireless sensor networks ACM/Kluwer Mobile Networks and Applications (MONET) (6): [7] Gupta P Kumar PR The capacity of wireless networks IEEE Trans on Information Theory (2): [8] Narayanaswamy S Kawadia V Sreenivas RS Kumar PR Power control in ad-hoc networks: Theory architecture algorithm and implementation of the COMPOW protocol In: Proc of the European Wireless Conf Florence [9] Kawadia V Protocols and architecture for wireless ad hoc networks [PhD Thesis] University of Illinois at Urbana- Champaign 2004

11 : 953 [10] Zhang X Lu SL Chen DX Xie L PREG: A practical power control algorithm based on a novel proximity graph for heterogeneous wireless sensor networks In: Cheng XZ Li W Znati T eds Proc of the 1st Int l Conf on Wireless Algorithms Systems and Applications (WASA) LNCS 4138 Berlin: Springer-Verlag [11] Kirousis LM Kranakis E Krizanc D Pelc A Power consumption in packet radio networks Theoretical Computer Science (1-2): [12] Clementi A Penna P Silvestri R On the power assignment problem in radio networks ACM/Kluwer Mobile Networks and Applications (MONET) 20049(2): [13] Kawadia V Kumar PR Power control and clustering in ad-hoc networks In: Mitchell K ed Proc of the IEEE Conf on Computer Communications (INFOCOM) New York: IEEE Press [14] Kubisch M Karl H Wolisz A Zhong LC Rabaey J Distributed algorithms for transmission power control in wireless sensor networks In: Yanikomeroglu H ed Proc of the IEEE Wireless Communications and Networking Conf (WCNC) New York: IEEE Press [15] Li L Halpern JY Bahl P Wang YM Wattenhofer R A cone-based distributed topology control algorithm for wireless multi-hop networks IEEE/ACM Trans on Networking (1): [16] Bahramgiri M Hajiaghayi MT Mirrokni VS Fault-Tolerant and 3-dimensional distributed topology control algorithms in wireless multihop networks In: Proc of the IEEE Int l Conf on Computer Communications and Networks (ICCCN) [17] Li N Hou JC Topology control in heterogeneous wireless networks: Problems and solutions In: Proc of the IEEE Conf on Computer Communications (INFOCOM) New York: IEEE Press [18] Wattenhofer R Zollinger A XTC: A practical topology control algorithm for ad-hoc networks In: Panda DK Duato J Stunkel C eds Proc of the Int l Parallel and Distributed Processing Symp (IPDPS) New Mexico: IEEE Press [19] Kumar S Lai TH Balogh J On k-coverage in a mostly sleeping sensor network In: Haas ZJ ed Proc of the ACM Int l Conf on Mobile Computing and Networking (MobiCom) New York: ACM Press [20] Berman P Calinescu G Shah C Zelikovsky A Efficient energy management in sensor networks In: Xiao Y Pan Y eds Proc of the Ad Hoc and Sensor Networks Series on Wireless Networks and Mobile Computing New York: Nova Science Publishers 2005 [21] Cerpa A Estrin D ASCENT: Adaptive self-configuring sensor networks topologies In: Stojmenovic I Olariu S eds Proc of the IEEE Conf on Computer Communications (INFOCOM) New York: IEEE Press [22] Ye F Zhong G Lu S Zhang L PEAS: A robust energy conserving protocol for long-lived sensor networks In: Stankovic J Zhao W eds Proc of the Int l Conf on Distributed Computing Systems (ICDCS) Providence: IEEE Press [23] Gui C Mohapatra P Power conservation and quality of surveillance in target tracking sensor networks In: Haas ZJ ed Proc of the ACM Int l Conf on Mobile Computing and Networking (MobiCom) New York: ACM Press [24] Xing GL Wang XR Zhang YF Lu CY Pless R Gill C Integrated coverage and connectivity configuration for energy conservation in sensor networks ACM Trans on Sensor Networks 20051(1):36 72 [25] Chen B Jamieson K Balakrishnan H Morris R SPAN: An energy efficient coordination algorithm for topology maintenance in ad hoc wireless networks ACM Wireless Networks 20028(5): [26] Heinzelman WR Chandrakasan AP Balakrishnan H Energy-Efficient communication protocol for wireless microsensor networks In: Nunamaker J Sprague R eds Proc of the Hawaaian Int l Conf on System Science (HICSS) Washington: IEEE Press [27] Ye M Li CF Chen GH Wu J EECS: An energy efficient clustering scheme in wireless sensor networks In: Dahlberg T Oliver R Sen A Xue GL eds Proc of the IEEE Int l Workshop on Strategies for Energy Efficiency in Ad Hoc and Sensor Networks New York: IEEE Press [28] Deng J Han YS Heinzelman WB Varshney PK Balanced-Energy sleep scheduling scheme for high density cluster-based sensor networks Elsevier Computer Communications Journal (Special Issue on ASWN 2004) (14): [29] Xu Y Heidemann J Estrin D Geography-Informed energy conservation for ad hoc routing In: Rose C ed Proc of the ACM Int l Conf on Mobile Computing and Networking (MobiCom) New York: ACM Press [30] Zhang B Mouftah H Efficient grid-based routing in wireless multi-hop networks In: Proc of the IEEE Symp on Computers and Communications (ISCC) Cartagena: IEEE Press

12 954 Journal of Software Vol18 No4 April 2007 [31] Deb B Bhatnagar S Nath B A topology discovery algorithm for sensor networks with applications to network management Technical Report DCS-TR-441 Rutgers University 2001 [32] Bao LC Garcia-Luna-Aceves JJ Topology management in ad hoc networks In: Gerla M ed Proc of the ACM Int l Symp on Mobile Ad-Hoc Networking and Computing (MobiHoc) New York: ACM Press [33] He GH Zheng R Gupta I Sha L A framework for time indexing in sensor networks ACM Trans on Sensor Networks 20051(1): [34] Amis AD Prakash R Huynh D Vuong T Max-Min d-cluster formation in wireless ad hoc networks In: Bauer F Irene K eds Proc of the IEEE Conf on Computer Communications (INFOCOM) Tel Aviv: IEEE Press [35] Younis O fahmy S HEED: A hybrid energy-efficient distributed clustering approach for ad hoc sensor networks IEEE Trans on Mobile Computing 20043(4): [36] Li XY Song WZ Wang Y Localized topology control for heterogeneous wireless sensor networks ACM Trans on Sensor Networks 20052(1): [37] Santi P Topology control in wireless ad hoc and sensor networks ACM Computing Surveys (2): [38] Burkhart M Rickenbach PV Wattenhofer R Zollinger A Does topology control reduce interference? In: Murai J Perkins CE Tassiulas L eds Proc of the ACM Int l Symp on Mobile Ad-Hoc Networking and Computing (MobiHoc) [39] Bisnik N Protocol design for wireless ad hoc networks: The cross-layer paradigm Technical Report Rennselaer Polytechnic Institute 2005 [40] Kawadia V Kumar PR A cautionary perspective on cross-layer design IEEE Wireless Communications (1):3 11 (1975 ) (1947 ) CCF (1970 ) (1942 ) CCF (1963 ) CCF

中文模板

中文模板 ISSN 1-9825 CODEN RUXUEW E-mail: jos@iscasaccn Journal of Software Vol18 No6 June 27 pp138 1318 http://wwwjosorgcn DOI: 1136/jos18138 Tel/Fax: +86-1-62562563 27 by Journal of Software All rights reserved