中文模板

Transcription

1 ISSN 1-985, CODN RUXUW -mail: Journal of Software, Vol18, No5, May 7, pp DOI: 1136/jos1819 Tel/Fax: by Journal of Software All rights reserved ADG: 1,+,, 3, 3, 1 1, 1 (, 6154) (, ) 3 ( ), 193) ADG: An nergy-aware Data Gathering Protocol for Wireless Sensor Networks LIU Ming 1,+, CAO Jian-Nong, CHN Gui-Hai 3, CHN Li-Jun 3, WANG Xiao-Min 1, GONG Hai-Gang 1 1 (School of Computer Science and ngineering, University of lectronic Science and Technology of China, Chengdu 6154, China) (Internet and Mobile Computing Laboratory, Department of Computing, Hong Kong Polytechnic University, Hong Kong, China) 3 (State Key Laboratory for Novel Software Technology (Nanjing University), Nanjing 193, China) + Corresponding author: -mail: winglm@gmailcom, Liu M, Cao JN, Chen GH, Chen LJ, Wang XM, Gong HG ADG: An energy-aware data gathering protocol for wireless sensor networks Journal of Software, 7,18(5): /18/19htm Abstract: In this paper, a hierarchical clustering protocol for long-lived sensor network is proposed ADG (an energy-aware data gathering protocol for wireless sensor networks) achieves a good performance in terms of lifetime by minimizing energy consumption for communications and balancing the energy load among all nodes ADG ads a new clustering parameter for cluster head election, which can better handle the hetergenous energy capacities Furthermore, it also ads a simple but efficient approach, namely intra-cluster coverage to cope with the fractional area coverage problem Through turning off redundant nodes, while the remaining nodes stay active to provide continuous service, the network lifetime can be significantly prolonged xperimental results have shown that ADG can satisfy the desired coverage fraction and outperform LACH (low energy adaptive clustering hierarchy), PGASIS (power-efficient gathering in sensor information systems) and DG (distributed energy-efficient data gathering and aggregation protocol) in terms of network lifetime Key words: : data gathering; energy-aware; clustering algorithm; intra-cluster coverage ADG(an energy-aware data gathering protocol for wireless sensor networks)adg,,adg,,adg, Supported by the National Natural Science Foundation of China under Grant No ( ); the National Grand Fundamental Research 973 Program of China under Grant No6CB33 ( (973)); the Hong Kong Polytechnic University under Grant NoA-PF77 ( ) Received ; Accepted 7-3-5

2 :ADG: 193,,,ADG, LACH(low energy adaptive clustering hierarchy),pgasis(power-efficient gathering in sensor information systems) DG(distributed energy-efficient data gathering and aggregation protocol) : ; ; : TP393 : A,,, ( ),,,,, [1], Ad Hoc, ( nodes/m 3[] ),,,,,, ( ), [3 9], ADG(an energy-aware data gathering protocol for wireless sensor networks),adg,,adg,,,adg (intra-cluster node scheduling), 1 3 ADG 4 5 1,,,,,,,, [3 1] Heinzelman [3] LACH(low energy adaptive clustering hierarchy),,lach p% (,p ),,,LACH,,,,,LACH Lindsey LACH PGASIS(power-efficient gathering in sensor information

3 194 Journal of Software Vol18, No5, May 7 systems) [4] PGASIS,,,,PGASIS LACH [5],,,,, Lee, [6] CODA (congestion detection and avoidance in sensor networks) CODA,,,,CODA, CODA, [7] HD(a hybrid, energy-efficient, distributed clustering approach) HD ( ) HD O(1), HD, HD,, [8 1] [8] AC(an emergent algorithm for highly uniform cluster formation), Soro [9], Ye CS(an energy efficient clustering scheme in wireless sensor networks) [1],,,CS,,, [11], 1 N M M A, :, A,, GPS,,,Berkeley Motes 1, [3 5,9] 3,, 3 : GPS ;,, [1], 4 5,, Berkeley Motes [13] 1,,,

4 :ADG: 195, :1),,, ;),,,, (sensing hole);3), ;4),,, ;,, (redeployment),, 4 3 LACH,,,LACH,, HD, CS,, 1 7, 3 4,, 3, 4 3, 5 6, 4, 5(3J) 1(97J) 6(9J) 7(16J) 3(13J) 4(173J) (13J) Fig1 Illustration of clusterhead election 1, 4 ADG, ADG 3 ADG,,, LACH,ADG,,,, 1

5 196 Journal of Software Vol18, No5, May 7 Table 1 Descriptions of states and messages 1 State Description Message Description Candidate Candidate for competing cluster head _Msg Tuple (selfid, self residual energy) Head Cluster head Head_Msg Tuple (selfid) Plain The member node of one cluster Join_Msg Tuple (selfid, headid) CH b The root node of routing tree Compete_Root_Msg Tuple (selfid, weight) 31 ADG,, [14], ID, ID, r _Msg,_Msg ID v i r, _Msg Table Node 4 s neighborhood table 4 ID State Residual energy (J) 3 Candidate 13 7 Candidate 16 6 Candidate 9 5 Candidate 3, a v i,v j (1 i m,i j) v i r,m, a m j= 1 V j a = (1) m a, () Head_Msg t residual a = k T () residual,k [9,1],T, residual a (),,ADG, a Head_Msg 1, a residual residual,, 4 3, 4, residual,adg ADG, t Head_Msg, Head_Msg t Head_Msg,, (t t,t+ t) Head_Msg,,, t Head_Msg Head_Msg,, t, t, Head_Msg, ADG,

6 :ADG: 197, Join_Msg Fig 3 1 state candidate broadcast Node_Residual_Msg 3 receive Node_Residual_Msg 4 update neighborhood table NT[] 5 t the broadcast delay time for competing a cluster head 6 while (the timer1(t) for cluster head election is not expired) 7 if (CurrentTime<t) 8 if (a Head_Msg is overheard from a neighbor NT[i]) 9 state plain 1 NT[i]state=head 11 else 1 continue 13 endif 14 else 15 if (state=candidate) 16 state head 17 broadcast Head_Msg 18 endif 19 endif endwhile 1 while (the timer for cluster join is not expired) if (state=plain && have not sended Join_Msg) 3 Send (Join_Msg to the nearest cluster head) 4 else 5 receive (Join_Msg from its neighbor plain nodes) 6 endwhile The pseudo-code for the algorithm of cluster formation Choi [15], : log(1 η) k = A + 4 A rs log A + 4 A rs + πrs,η ( A ),k,r s,,,,,,,,,,, (3) η k,, k 1,, 3 (,, ),,,, η (3)

7 198 Journal of Software Vol18, No5, May 7 (a) Illustration of active nodes before scheduling (b) Illustration of active nodes after scheduling (a) (b) Fig3 The comparison of the number of active nodes in the period of pre-schedule and scheduled respectively 3,, η,, 33, CH b CH b,,, r c, 4 CH b, Comp_Root_Msg : D( RSstr ) a pb = ρ (4) D( RS max ),RS str ok,rs max ok,d,ρ, max, CH b, ρ, ρ=1 ρ, (4),, CH b :1) ;) CH b,,ch b, D(RS str ) CH b, a,, CH b, a CH b a, max 4(a), G 7,, 1 CH b, 1 Comp_Root_Msg(1,1,4), 3 3 (1,1,4), ID,, (1,,4) (1,3,4), (1,,4), 5 (1,5,4), 3 (1,3,4),, 4(b) G, p b CH b,

8 :ADG: (1,4,4) 6 4 (1,,4) (1,1,4) (1,5,4) 5 (1,,4) 3(1,1,4) (4,4,5) 6 4 (a) (4,4,5) (4,6,5) 5 (4,,5) (1,3,4) 3 (1,1,4) (4,,5) 1 (4,,5) (b) Cluster head Candidate of CH b () The second CH b _Msg received by one cluster head () The first CH b _Msg received by one cluster head CH b _Msg=(ID of Fi candidate, ID of transmitter, ρ b of candidate) Fig4 The algorithm of routing tree construction 4 4, ADG 1,ADG : ADG, (), (Head_Msg) t T Head_Msg, t, t Head_Msg, t Head_Msg, Head_Msg T,, Head_Msg : p C nexp 1 t 1 T nexp 1 πr,n exp, nexp = N,N t A, r=15m, A =(1 1)m,N=1, t=1ms,t=1s, 1 p 994, T, r c p A A k max =, k min =,, A 3r 3 3r :,,, [16], 1,, ; [17] 3 (overlapping angle)θ (5)

9 11 Journal of Software Vol18, No5, May 7 π/3( 5 ) 3, ( 6 ) 6, A 6 (B,C,D,,F,G), r c +ε,,ε,r c, r c, A 6 6, A 3 r c, 3r, A k max = 3r c c C G B B F A C A D Fig7 F Fig5 G The maximal overlap angle among three neighboring clusterheads Fig6 Illustration of minimal area of cluster 5 6 A r ε B C 7, A 6 3( r ε ),ε, 3r c, 7 A 3, 3 3 D c, Illustration of maximal area of cluster A k min = [18] A 7 3 3r c,, C i, 3r / C 3 3r / r c r c i c c r c,,, k r exp 4 A = 3 3r c 3 N A, π A DA = 4, 7Nε fs :,(round) (frame) l, : member = l elec + lε d fs toch 4 A, 3 3 r c r c (6) π π 3 [ toch ] = ρ r d rdθ d 3 3 r c (7)

10 :ADG: 111 4, ρ = 3 3 r c 9 [ ] d toch = r c (8) 8 3π, member 9 = lelec + lε fs rc (9) 8 3π, 3 : Routing Tree Routing Tree, r c, Ch N N = lelec + l elec 1+ Ne ave + l DA + Ne ave + 4lε fsrc (1) k exp k exp,ne ave =1 Spanning Tree, Cluster N = Ch + 1 k exp total = k exp = Nl cluster elec member N N N k = exp l elec l DA lε fsrc + 1 l k exp k exp k exp 4 A A 9 A + NlDA + lda + 16lε Nl r l fs + ε fs c ε fs 3 3r π c elec + lε fs 9 r c 8 3π r,, : r π A (11) (1) DA = 4 (13) 7Nε fs, A =1 1, N=1,ε fs =1pJ, DA =5nJ/bit/signal, r c =7719m, 4 O(N) : ADG, (round),, 1 Join_MSG,, Head_Msg ; Spanning Tree, 1 Candidate_Msg, ;, Candidate_MSG Candidate_Msg, CH b, Child_Msg Spanning 3N A ε fs Tree, (, k = ): π N k + k 1 total message overhead N k, O(N) 5 O(N) : ADG, Routing Tree A,, + k + k 1 DA (14)

11 11 Journal of Software Vol18, No5, May 7 πr N A, : πr informatio n stored N + k A, O ( N ) 5 r 4 A, ADG, k exp = 3 3r π A DA = 4 7Nε fs, ADG, 5, 5,, 1,, 3 : 1 (first node die, FND), 1 ; (half nodes die, HND), ; (last node die, LND), 3 Table 3 Simulation parameters 3 Parameter Value Network size (1 1), (15 15), ( ), (5 5), (3 3), (35 35), (4 4) Sink position (5,175), (5,), (5,15), (5,3), (5,45), (5,6), (5,75), (5,3), (5,4) Node number 1, 15,, 5, 3, 35, 4, 45, 5 Threshold distance (d ) (m) 75 Cluster radius (r) (m) 15,, 5, 3, 35, 4 Sensing range r s (m) 15,, 5 elec (nj/bit) 5 e _fs (pj/bit/m ) 13 e _amp (pj/bit/m 4 ) 13 _fusion (nj/bit) 5 Data packet size (bytes) 5, 1, 15,, 5, 5 Control message size (bytes) 5 Packet header size (bytes) 5 5 TDMA frames Initial energy (J) Qos requirement 9, ADG ADG, (5nodes,1 1m ) (1nodes,1 1m ) 511 vs 8(a),,,,, NπR,, ρ = 8(b),, A,, 8(a) 8(b),, (15)

12 :ADG: 113 The number of cluster heads Simulation results Analytical results The number of cluster heads Cluster range Cluster range (a) 1 nodes (b) 5 nodes Fig8 (a) (b) 5 The number of clusterheads: Analytical results vs simulation results Simulation results Analytical results (a), 1 1m 1, m, 87 3 : 7719m, 9(b), 1 1m 5, 15m m,, nodes 5 nodes Cluster range (a) Fig9 5 ADG Cluster radius vs network lifetime Cluster range 9 vs, ADG DIRCT,LACH,PGASIS DG(distributed energy-efficient data gathering and aggregation protocol) [19] 4 51 : 1 1m, 1 5, (5,), 1% ( ) ,DG ADG, 1, 4,DG ADG,,DG ADG, DG ADG,, DG ADG, (b)

13 114 Journal of Software Vol18, No5, May 7,,DG ADG 11, ADG, LACH,,,,,, PGASIS,, DG, ADG,,,,ADG, 11, 1 5, (FND),, Fig1 DIRCT PGASIS ADG LACH DG DIRCT PGASIS ADG LACH DG The number of dead nodes The number of dead nodes Timing of nodes death (1 nodes) 1 (1 nodes) Fig11 Timing of nodes death (5 nodes) 11 (5 nodes) : 1 1m, 1, (5,175) (5,4),DG ADG 3m, 1% ( ) 1~ 15,,,, PGASIS,DG ADG, DIRCT LACH LACH PGASIS,,, 1,DG ADG (FND) PGASIS,, 13~ 15,,DG ADG 3, 1 15, LACH PGASIS, 15,DG ADG 3,, 53 : 1 1m ~4 4m, 1, 1m,DG ADG 3m, 1% ( ) 16~ 19 15~ 18,DG ADG, 4 4m,5 (FND), DG ADG,

14 :ADG: 115,,,,,,, Sink node position Fig1 DIRCT PGASIS LACH DG Sink node position vs network lifetime (FND) ADG 1 vs (FND) DIRCT PGASIS LACH DG ADG Sink node position Fig13 Sink node position vs network lifetime (HND) 13 vs (HND) 1 5 DIRCT LACH DIRCT PGASIS DG 45 PGASIS 1 ADG Sink node position Fig14 Sink node position vs network lifetime (LND) 14 vs (LND) Fig16 DIRCT PGASIS ADG LACH DG The total number of sensing data Fig15 LACH DG ADG The distance between sink node and network The amount of gathered data 15 DIRCT PGASIS ADG LACH DG Sink node position The size of network The area of monitored region vs network lifetime (FND) 16 vs (FND) Fig17 The area of monitored region vs network lifetime (HND) 17 vs (HND)

15 116 Journal of Software Vol18, No5, May Heads number of DG The number of Connected subgraph of DG Heads number of ADG The number of connected subgraph of ADG Fig18 Value DIRCT LACH PGASIS DG 1 ADG The size of network The area of monitored region vs network lifetime (LND) 18 vs (LND) Fig19 3 The size of network The number of clusterheads and the connected component consisted by clusterheads 19 19,DG ADG,, 1,,,, 19, 4 4m, 6,, 17, 4 4m,, DG ADG 1 1m, 9, 54 : 1 1m, 1~5, 3m 1m, (5,), 9% 99%, 1 1 DG_C ADG_C DG ADG, DG ADG DG ADG,,,,,,,,,, Fig DG DG_C ADG ADG_C DG ADG DG_C ADG_C The number of nodes The number of nodes The number of nodes vs network lifetime (QoS=9%) vs (QoS=9%) Fig1 The number of nodes vs network lifetime (QoS=99%) 1 vs (QoS=99%)

16 :ADG: : 1 1m, 1~6, 3m 1m, (5,), 7%~99%, 3 Obtained QoS Fig Nodes=1 Nodes= Required QoS (coverage fraction) Simulation coverage fraction vs desired coverage fraction vs The number of active nodes Fig3 QoS=85 QoS= QoS=9 QoS=99 5 The number of deployed nodes The number of active nodes vs the number of deployed nodes 6 3 vs, ADG, ADG,, 1, 95%,,,,, 3, 3, 85%, 7, 99%, 18, 56 : 1 1m, 1, 3m 1m, (5,),, (1J,J) (5J,J) 4 5 DIRCT,LACH PGASIS 3, DG, ; ADG, 4 5,,ADG DG 6%;,ADG DG 15%, ADG 6,,, ADG,ADG : (1), LACH,HD,

17 118 Journal of Software Vol18, No5, May 7 () ADG, (3) ADG, (4), ADG Fig4 DIRCT PGASIS ADG LACH DG The number of dead nodes Timing of nodes death in high heterogeneous energy scenario Fig5 DIRCT PGASIS ADG LACH DG The number of dead nodes Timing of nodes death in moderate heterogeneous energy scenario 4 5, MOTS ADG, ADG, ADG References: [1] Shih, Cho S, Ickes N, Min R, Sinha A, Wang A, Chandrakasan A Physical layer driven protocol and algorithm design for energy-efficient wireless sensor networks In: Basagni S, Sivalingam K, eds Proc of the 7th Annual Int l Conf on Mobile Computing and Networking (MobiCom 1) San Diego: ACM Press, [] Tilak S, Abu-Ghazaleh NB, Heinzelman W Infrastructure tradeoffs for sensor networks In: Raghavendra CS, Sivalingam K, eds Proc of the 1st Int l Workshop on Wireless Sensor Networks and Applications (WSNA ) Atlanta: ACM Press, [3] Heinzelman WR, Chandrakasan A, Balakrishnan H nergy-fficient communication protocol for wireless microsensor networks In: Proc of the Hawaii Int l Conf on System Sciences San Francisco: I Computer Society, [4] Lindsey S, Raghavendra CS PGASIS: Power efficient gathering in sensor information systems In: Proc of the I Aerospace Conf San Francisco: I Computer Society, 1 6 [5] Heinzelman WR, Chandrakasan A, Balakrishnan H An application-specific protocol architecture for wireless microsensor networks I Trans on Wireless Communications,,1(4):66 67 [6] Lee SH, Yoo JJ, Chung TC Distance-Based energy efficient clustering for wireless sensor networks In: Proc of the 9th Annual I Int l Conf on Local Computer Networks (LCN 4) 4 [7] Younis O, Fahmy S Distributed clustering in ad-hoc sensor networks: A hybrid, energy-efficient approach In: Zhang ZS, Low S, eds Proc of the I INFOCOM San Francisco: I Computer Society Press, 4 [8] Chan H, Perrig A AC: An emergent algorithm for highly uniform cluster formation In: Proc of the 1st uropean Workshop on Sensor Networks (WSN) LNCS 9, Berlin: Springer-Verlag, [9] Soro S, Heinzelman WB Prolonging the lifetime of wireless sensor networks via unequal clustering In: Proc of the 19th I Int l on Parallel and Distributed Processing Symposium San Francisco: I Computer Society Press, [1] Ye M, Li CF, Chen G, Wu J CS: An energy efficient clustering scheme in wireless sensor networks In: Dahlberg T, Oliver R, Sen A, Xue GL, eds Proc of the I IPCCC 5 New York: I Press, [11] Shen B, Zhang SY, Zhong YP Cluster-Based routing protocols for wireless sensor networks Journal of Software, 6,17(7):

18 :ADG: (in Chinese with nglish abstract) [1] Stojmenovic I Position based routing in ad hoc networks I Communications Magazine,,4(7): [13] Hill J, Szewczyk R, Woo A, Hollar S, Culler D, Pister KSJ System architecture directions for networked sensor ACM SIGPLAN Notices,,11(35):93 14 [14] Wu K, Gao Y, Li F, Xiao Y Lightweight deployment-aware scheduling for wireless sensor networks Mobile Networks and Applications, 5,1(6): [15] Choi W, Das SK Trade-Off between coverage and data reporting latency for energy-conserving data gathering in wireless sensor networks In: Hubaux JP, Makki K, Zhou C, La Porta T, eds Proc of I Int l Conf on Mobile Ad-hoc and Sensor Systems (MASS 4) San Francisco: I Computer Society Press, [16] Yang S, Dai F, Cardei M, Wu J, Patterson F On connected multiple point coverage in wireless sensor networks Journal of Wireless Information Networks, 6,13(4):89 31 [17] Choudhury RR, Kravets R Location-Independent coverage in wireless sensor networks 4 pubs [18] Williams R The Geometrical Foundation of Natural Structure: A Source Book of Design New York: Dover Publication Inc, [19] Liu M, Gong HG, Mao YC, Chen LJ, Xie L A distributed energy-efficient data gathering and aggregation protocol for wireless sensor networks Journal of Software, 5,16(1): (in Chinese with nglish abstract) /16/16htm : [11],,,6,17(7): htm [19],,,,,5,16(1): (197 ),,,,,, (1961 ),,,,, Qos (196 ),,,,,CCF, (1978 ),,,,, (1963 ),,,,,CCF, (1975 ),,,,,