686 36,..,,, (Low-energy adaptive clustering hierarchy, LEACH),,. (Time division multiple access, TDMA). [15],,. [16] TDMA,. [17],,,. [18] (Signal to

Size: px

Start display at page:

Download "686 36,..,,, (Low-energy adaptive clustering hierarchy, LEACH),,. (Time division multiple access, TDMA). [15],,. [16] TDMA,. [17],,,. [18] (Signal to"

欣积禹
5 years ago
Views:

1 36 5 Vol. 36, No ACTA AUTOMATICA SINICA May, (Wireless sensor network, WSN).,,.,,. /,.,. DOI,,,, /SP.J Markov Chain-based Distributed Scheduling Approach for Wireless Sensor Network NIU Jian-Jun 1 DENG Zhi-Dong 1 Abstract Energy efficiency is one of the core issues of wireless sensor network (WSN). For battery powered WSN, the energy constraint restricts the lifetime of WSN, which poses great challenges to its large scale application. In this paper, we propose a collaborative distributed scheduling approach based on Markov chain, which is applicable to real WSN. We prove that this approach is convergent. This approach can not only schedule wake-up and sleep states of nodes, but also schedule the data transmission of nodes to reduce the collision of data packets. The simulation results show that the proposed approach can save energy effectively and has less effect on other performances of the network. Key words Wireless sensor network (WSN), energy efficiency, scheduling, Markov chain, distributed (Wireless sensor network, WSN),. Sink, [1]. 20, [2 5]..,,,,,, [6 7]., WSN, Manuscript received March 13, 2009; accepted October 23, 2009 (863 ) (2006AA04Z208, 2006AA ) Supported by National High Technology Research and Development Program of China (863 Program) (2006AA04Z208, 2006A A040102) 1. ( ) State Key Laboratory of Intelligent Technology and Systems, Tsinghua National Laboratory for Information Science and Technology, Department of Computer Science and Technology, Tsinghua University, Beijing [8] ; /,, [9]., [10],,,. [11],.,. [12],. [13],.,,. [14] 15., (Random independent scheduling, RIS),.,, (Maximization of sensor network life, MSNL) (Linear distance-based scheduling, LDS), Sink., (Lightweight deploymentaware scheduling, LDAS),

2 686 36,..,,, (Low-energy adaptive clustering hierarchy, LEACH),,. (Time division multiple access, TDMA). [15],,. [16] TDMA,. [17],,,. [18] (Signal to interference plus noise ratios, SINR),,. TDMA,,,,., [19],,.,. [20],. [21 22]., (Discrete time Markov chain, DTMC).,. [23],, DTMC..,.,,,., WSN,,,.,, [23], (Markov chain-based scheduling approach, MBSA).,,.,., WSN,. : 1) CSMA/CA, WSN. 2) MBSA.,.,,. 3) MBSA,. 4) CSMA/CA,.,. : 1 ; 2 MBSA, ; 3, ; 4. 1.,, Sink,. Sink, Sink.,.,.. 1.1, (T) (R) (I) (S)..,,.,,.,. 1.,,.,.

3 5 : Fig. 1 Duty cycle of a node,, (First input first output, FIFO)., FIFO., FIFO,. FIFO.,,. 1.2 MAC MAC CSMA/CA [24]. CSMA/CA, RTS/CTS. 1.3, WSN.,,. Sink. MBSA, : Sink.,,.,.., Sink., Sink,. B A, A B, B A. A.,.,. TDMA.,, TDMA. 1.5 WSN....,, ;. 2, WSN DTMC,. MBSA : ;, ;,. 2.1 ; MBSA, ; , MBSA. 2.1,.,,.,,. MAC. IEEE DCF CSMA/CA [24],,, MAC. RTS/CTS, RTS., : (F). F, ;.,,

4 688 36, ;,,.. FIFO,, ;,,.,., FIFO, ; FIFO,., FIFO (I 0 ) FIFO (I x )., 2.,, DTMC. Fig. 3 3 State transition of child nodes,,, F., F,. g p.,, β , (Routing discovery), MBSA. MBSA (Data delivery, DD) (Scheduling update, SU).,. Fig. 2 2 State transition diagram of a node 2, S T R F, I 0 I x FIFO.,.,.,, ;,., : (M) (V), 3. M ( ); V., M,. V,., v, m. Fig System working diagram.,.,. : 1).. FIFO. 2),., ;,. 3) FIFO,,,

5 5 : 689.,. 4). 5).,. 2.4 (Upstream update) (Downstream update). 5., N 1 N k N m, N m N n. Fig. 5 5 MBSA Scheduling update procedure in MBSA 1).,,.,,.,, (1) (2) v m. v = t j t a j ch (1) m = (1 t j ) t a (2) j ch, ch, t j j, t a. 2), F., F., Sink,,..,, (3) F S. g = g p (1 v) (3), g F S, g p F S., F S.., F S.,, F S.,,., F., F., F S. : Sink ; Sink, F S I 0 S. 3) CSMA/CA, (4) β. RTS/CTS CSMA/CA, RTS (4).. β = (4), 1 (Scheduling matrix, SM). 0., 2.1. p(t R) = m β,,,.,. CSMA/CA MBSA,, R F. MAC CSMA/CA., MAC. MAC,,

6 MBSA, F. 1,. Table 1 1 State scheduling probabilities S i S i+1 P (S i+1 S i) S I 0/I x 1,.., WSN.,. 6, MBSA, SM i i, SP i i, DD i SU i i. I 0 S 1 v I 0 I 0/R v R T m β R I x 1 m β I x I x/r 1 (1 v) β I x T (1 v) β T I x/f 1 (1 v) β T T (1 v) β F I x 1 g p (1 v) F S g p (1 v) 1, 1, 2, 3., FIFO, I 0, I x. A/B A B, 3 A B.,,.,,,,,.,, v, F S I 0 S.,. 2.5 MBSA, WSN, 6.,,. 1 v, m, g, β, (Scheduling parameter, SP).. 6,, Fig The sequence of scheduling parameters,,., CSMA/CA, (Short interframe space, SIFS), ( ) (Distributed (coordination function) interframe space, DIFS), (Extended interframe space, EIFS), ( ) (Point (coordination function) interframe space, PIFS) Slottime SIFS [24],., (1) (2), v, m. (1) (3), g,. β,. k, n SP n = (t n a, t n 1, t n 2,, t n k, g n, β n )..,. H L,,,,,. 1. MBSA, {SP n, n N 0, SP n H L }.. H L, MBSA, SP n SP n 1,,

7 5 : 691., {SP n, n N 0, SP n H L }.,,. SP n H L, SP n+1 H L, P (SP n+1 SP n ) > 0, SP n+1 H L, SP n H L, P (SP n+1 SP n ) > 0, {SP n, n N 0, SP n H L }. 1.,.. [25] ,,. [25] 3.5.6,. [25] 3.5.8,. 2. {SP n, n N 0, SP n H L } MBSA, P = (p i,j ).., MBSA, {SP n, n N 0, SP n H L }. 1, P = (p i,j ) π L,. WSN., β,. β, ;.,., n, SP n G = (t n 1, t n 2,, t n N, t n a1, t n a2,, t n an), t n i, t n ai i n, ; N WSN. H G,. 3. WSN. MBSA, WSN {SPG, n n N 0, SPG n H G }.. 1. H L,, H G. SPG n,. SP n 1 G,., {SPG, n n N 0, SPG n H G }., SPG n H G, SP n+1 G H G, P (SP n+1 G SP G) n > 0, SP n+1 G H G, SP n G H G, P (SP n+1 G SP n G) > 0, {SPG, n n N 0, SPG n H G }. 4. {SPG, n n N 0, SPG n H G } MBSA WSN, P = (p i,j).. 3, {SPG, n n N 0, SPG n H G }. 1, P = (p i,j) π G,., MBSA,,.. [26] {U S, A[i], q( i, a), r(i, a), V, i U S, a A[i]}, U S, A[i] i, q( i, a) i a, r(i, a) i a ( ), V,. V [i] 0 i,. 2., Q, V, 1 V = lim N N + 1 N Q n r = Q r n=0, Q Q.

8 [27] WSN, MBSA,.. 1 WSN MBSA, 6, DD, SU,. SU, i SP i, H L. (1) (3) 1, SM i SP i., SP i A(SP i ) = {SM i }., p(sp i+1 SP i ) SP i SM i, SP i+1. e(sp i ) SP i SM i, MBSA. 1,., N Ē = lim N 1 N + 1 n=0 P n e 2, P. P P, 2, Ē, Ē = P r P P, Ē.,., : WSN,.,.,, 4 ;,, 2., MAC.,. MBSA WSN. 3 MBSA, NS2, RTS/CTS CSMA/CA,. 3.1 WSN 200, m, Sink., Sink. 250 m. Crossbow IRIS [28], 2. IRIS RAM MICAZ,. IRIS T R I IRIS W, 0.07 W, W, W.. Table 2 2 Energy model of nodes states T R I S 250 Kbps, , 10, 60,.,.,..,. FIFO,., MBSA (Non-MBSA) CSMA/CA, ; CSMA/ CA MBSA. MBSA 0, 1,. 20,

9 5 : 693 MBSA 40,,. 3. Table 3 3 Parameters setting for simulations m m W 0.07 W W W 250 Kbps , : 1) :, (W). 2) :, FIFO,. 3) :, Sink (Bps). 4) :, Sink, (s). 20, 4. 4, MBSA,. MBSA,, ; MBSA,, ;, MBSA,. MBSA /., MBSA, Non-MBSA. 7,, MBSA Non-MBSA,., MBSA CSMA/CA Non-MBSA. 8.,,,,,,. 8., MBSA, Table 4 4 Simulation results Non-MBSA MBSA (W) ( ) (Bps) (s) Fig. 7 Average energy consumption with the hop of nodes 9 10,,, MBSA,. 4.,

10 694 36,,,.. References 1 Akyildiz L F, Su W, Sankarasubramaniam Y, Cayirci E. A survey on sensor networks. IEEE Communication Magazine, 2002, 40(8): Fig. 8 Fig. 9 8 Average energy consumption with the number of descendant nodes 9 Total energy consumption of WSN system at each iteration 2 Ren Feng-Yuan, Huang Hai-Ning, Lin Chuang. Wireless sensor networks. Journal of Software, 2003, 14(7): (,,.., 2003, 14(7): ) 3 Mainwaring A, Culler D, Polastre J, Szewczyk R, Anderson J. Wireless sensor networks for habitat monitoring. In: Proceedings of the 1st ACM International Workshop on Wireless Sensor Networks and Applications. Atlanta, USA: ACM, Kim S, Pakzad S, Culler D, Demmel J, Fenves G, Glaser S. Health Monitoring of Civil Infrastructures Using Wireless Sensor Networks, Technical Report No. UCB/EECS , Electrical Engineering and Computer Sciences, University of California at Berkeley, USA, Tran D A, Nguyen T. Localization in wireless sensor networks based on support vector machines. IEEE Transactions on Parallel and Distributed Systems, 2008, 19(7): Sun Li-Min, Li Jian-Zhong, Chen Yu. Wireless Sensor Network. Beijing: Tsinghua University Press, (,,.. :, ) 7 Goldsmith A J, Wicker S B. Design challenges for energyconstrained Ad Hoc wireless networks. IEEE Wireless Communications, 2002, 9(4): Amit S, Anantha C. Dynamic power management in wireless sensor network. IEEE Design and Test, 2001, 18(2): Jiang Hua, Zheng Chun-Lei, Liu Hai-Tao. Research of link level energy efficiency strategy in wireless sensor networks. Chinese Journal of Sensors and Actuators, 2006, 19(6): (,,.., 2006, 19(6): ) 10 Wang B, Han Z, Liu K J R. Distributed relay selection and power control for multiuser cooperative communication networks using buyer/seller game. In: Proceedings of the 26th IEEE International Conference on Computer Communications. Alaska, USA: IEEE, Fig. 10 Energy consumption on the nodes of No. 90 and No. 180 at each iteration.,.. 11 Chang T J, Wang K, Hsieh Y L. A color-theory-based energy efficient routing algorithm for mobile wireless sensor networks. Computer Networks, 2008, 52(3): Chatterjea S, Nieberg T, Meratnia N, Havinga P. A distributed and self-organizing scheduling algorithm for energyefficient data aggregation in wireless sensor networks. ACM Transactions on Sensor Networks, 2008, 4(4): Liu Song, Zhong Chong-Quan, Teng Hong-Fei, Zhou Qian, Song Ben-Jie. Research and implementation of node adaptive sleep schedule algorithm for wireless sensor networks.

5 : 695 Chinese Journal of Sensors and Actuators, 2008, 21(10): 1755 1759 (,,,,. NASS., 2008, 21(10): 1755 1759) 14 Wang L, Xiao Y.

A distributed policy scheduling for wireless sensor networks. In: Proceedings of the 26th IEEE International Conference on Computer Communications. Alaska, USA: IEEE, 2007.

11 5 : 695 Chinese Journal of Sensors and Actuators, 2008, 21(10): (,,,,. NASS., 2008, 21(10): ) 14 Wang L, Xiao Y. A survey of energy-efficient scheduling mechanisms in sensor networks. Mobile Networks and Applications, 2006, 11(5): Chen Y, Fleury E. A distributed policy scheduling for wireless sensor networks. In: Proceedings of the 26th IEEE International Conference on Computer Communications. Alaska, USA: IEEE, Yao Y, Giannakis G B. Energy-efficient scheduling for wireless sensor networks. IEEE Transactions on Communications, 2005, 53(8): Wu Yan-Ping, Liu Ming, Ye Juan. Time-slot scheduling algorithm based on weighted traffic load in wireless sensor networks. Journal of Computer Applications, 2007, 27(12): (,,.., 2007, 27(12): ) 18 Lu G, Krishnamachari B. Energy efficient joint scheduling and power control in wireless sensor networks. In: Proceedings of the 2nd IEEE International Conference on Sensor and Ad Hoc Communications and Networks. Santa Clara, USA: IEEE, Visweswara S C, Dutta R, Sichitiu M L. Adaptive Ad Hoc self-organizing scheduling for quasi-periodic sensor network lifetime. Computer Communications, 2006, 29(17): Cohen R, Kapchits B. An optimal wake-up scheduling algorithm for minimizing energy consumption while limiting maximum delay in a mesh sensor network. IEEE/ACM Transactions on Networking, 2009, 17(2): Randeep B, Abhishek K, Li L. The power balancing problem in energy constrained mlti-hop wireless networks. In: Proceedings of the 26th IEEE International Conference on Computer Communications. Alaska, USA: IEEE, Altman E, Avrachenkov K, Miller G, Prabhu B. Discrete power control: cooperative and non-cooperative optimization. In: Proceedings of the 26th IEEE International Conference on Computer Communications. Alaska, USA: IEEE, Chiasserini C F, Garetto M. An analytical model for wireless sensor networks with sleeping nodes. IEEE Transactions on Mobile Computing, 2006, 5(12): Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, ANSI/IEEE Standard , Lin Yuan-Lie. Applied Stochastic Process. Beijing: Tsinghua University Press, 2002 (.. :, 2002) 26 Hu Qi-Ying, Liu Jian-Yong. An Introduction to Markov Decision Processes. Xi an: Xidian University Press, 2000 (,.. :, 2000) 27 Liu Ke. Applied Markov Decision Process. Beijing: Tsinghua University Press, 2004 (.. :. 2004) 28 MPR-MIB Users Manual (Revision A) [Online], available: June 6, njj05@mails.tsinghua.edu.cn (NIU Jian-Jun Ph. D. candidate in the Department of Computer Science, Tsinghua University. His research interest covers wireless sensor networks and computational intelligence.),... michael@tsinghua.edu.cn (DENG Zhi-Dong Ph. D., professor in the Department of Computer Science, Tsinghua University. His research interest covers wireless sensor network, intelligent robot, computational biology, computational intelligence, complex network theory, and virtual reality technology. Corresponding author of this paper.)

Microsoft PowerPoint - Aqua-Sim.pptx

Microsoft PowerPoint - Aqua-Sim.pptx Peng Xie, Zhong Zhou, Zheng Peng, Hai Yan, Tiansi Hu, Jun-Hong Cui, Zhijie Shi, Yunsi Fei, Shengli Zhou Underwater Sensor Network Lab 1 Outline Motivations System Overview Aqua-Sim Components Experimental