王 旭，梁 英

(沈陽理工大學，信息科學與工程學院，遼寧 沈陽 110159)

面向服務質(zhì)量的WSN節(jié)能調(diào)度算法

王 旭，梁 英

(沈陽理工大學，信息科學與工程學院，遼寧 沈陽 110159)

為合理使用有限的無線傳感器網(wǎng)絡(wirless sensor network,WSN)能量資源，為用戶提供有保證的網(wǎng)絡服務應用，采用通過節(jié)點調(diào)度來合理組織網(wǎng)絡中節(jié)點的工作狀態(tài)，并且按照滿足一定實時性的可靠性路由算法傳輸數(shù)據(jù)的方式，提出了一種面向服務質(zhì)量的WSN節(jié)能調(diào)度算法，算法分為節(jié)點狀態(tài)調(diào)度和基于服務質(zhì)量(quality of service,QoS)的路由協(xié)議兩部分，并且對其進行仿真。仿真結(jié)果證明，算法在數(shù)據(jù)傳輸?shù)膶崟r性和可靠性方面性能優(yōu)越，可擴展性好，并且節(jié)約了能量，延長了網(wǎng)絡生存周期。

無線傳感器網(wǎng)絡；節(jié)能；服務質(zhì)量；網(wǎng)絡生存周期

隨著微電子、計算機和網(wǎng)絡技術(shù)的發(fā)展，傳感器技術(shù)正向著微型化、智能化、網(wǎng)絡化、集成化的方向發(fā)展，無線傳感器網(wǎng)絡作為傳感器技術(shù)的傳輸手段和重要支撐技術(shù)，已經(jīng)成為傳感器領(lǐng)域的研究熱點。

無線傳感器網(wǎng)絡是以數(shù)據(jù)為中心的網(wǎng)絡，高效準確地完成用戶指定的任務是衡量網(wǎng)絡性能的首要標準。因此，合理使用有限的網(wǎng)絡資源為用戶提供有保證的網(wǎng)絡服務應用，成為無線傳感器網(wǎng)絡服務質(zhì)量體系研究的主要目標。無線傳感器一般具有節(jié)點密度較大的特點，傳感器節(jié)點一般靠電池供電，工作在無人值守、惡劣的工作環(huán)境當中，使得能量管理問題顯得尤為重要。

無線傳感器網(wǎng)絡為了節(jié)省能量，需要對傳感器節(jié)點進行節(jié)能調(diào)度，或者盡可能減少節(jié)點間的通信對能量的消耗，結(jié)合傳感器節(jié)點大量冗余的特點，使一些節(jié)點休眠并且不會影響網(wǎng)絡的覆蓋服務質(zhì)量。算法同時要兼顧網(wǎng)絡能量的均衡和計算復雜度。節(jié)點調(diào)度算法已經(jīng)有PEAS、CCP等。PEAS算法中，傳感器節(jié)點有睡眠、探測和工作三種狀態(tài)，節(jié)點初始為睡眠狀態(tài)，經(jīng)過一段時間后進入探測狀態(tài)，處于探測狀態(tài)的節(jié)點發(fā)送廣播消息，根據(jù)鄰居節(jié)點的應答消息決定是否進入工作狀態(tài)。PEAS算法計算簡單，但是不能保證監(jiān)測區(qū)域的完全覆蓋，并且通信開銷大，CCP算法為了避免一個節(jié)點死亡，多個節(jié)點接替工作的沖突發(fā)生，引入了加入和退出狀態(tài)。CCP算法利用判斷節(jié)點冗余性的方法，節(jié)約網(wǎng)絡能量的同時保證對監(jiān)測區(qū)域的全覆蓋，但節(jié)點周期性的廣播信息使得通信開銷較大，并且沒有均衡利用網(wǎng)絡能量，節(jié)點失效嚴重。

無線傳感器網(wǎng)絡不僅要保證感知覆蓋質(zhì)量，還要保證數(shù)據(jù)傳輸?shù)馁|(zhì)量，因此需要設(shè)計QoS路由協(xié)議，已有的QoS路由協(xié)議有SAR協(xié)議和SPEED協(xié)議等。SAR路由協(xié)議通過建立以匯聚節(jié)點為根的多播樹實現(xiàn)源節(jié)點與匯聚節(jié)點的多條傳輸路徑，提供了QoS保證，其缺點是網(wǎng)絡能耗較大，沒有考慮實時性的要求。SPEED協(xié)議設(shè)計了延遲估計機制獲得網(wǎng)絡負載情況、SNGF路由算法和鄰居反饋機制選擇滿足一定傳輸速率的節(jié)點、反向壓力變更路由避免擁塞和路由空洞，可靠性、實時性較好，算法為分布式，可擴展性好，但沒有考慮節(jié)能的要求，導致傳輸速率高的節(jié)點可能因為過多的承擔數(shù)據(jù)傳輸任務而過早死亡。本文提出QoS路由在數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點的選擇當中考慮了剩余節(jié)點能量，均衡了網(wǎng)絡能量分布，從而延長了網(wǎng)絡生存周期。當網(wǎng)絡發(fā)生擁塞時，選擇其它路徑傳輸數(shù)據(jù)，增強了網(wǎng)絡的可靠性。

1 系統(tǒng)模型

所有傳感器節(jié)點隨機部署在一個長方形區(qū)域A中，節(jié)點密度足夠大，若所有節(jié)點都處于工作狀態(tài)，可以完全覆蓋監(jiān)測區(qū)域A，現(xiàn)假設(shè)監(jiān)測區(qū)域滿足如下條件：

(1)監(jiān)測區(qū)域A相對于單個節(jié)點對監(jiān)測區(qū)域的覆蓋范圍足夠大，所以邊界節(jié)點對于網(wǎng)絡的影響可以忽略不計。

(2)傳感器網(wǎng)絡的節(jié)點被隨機布撒到監(jiān)測區(qū)域當中，節(jié)點到達監(jiān)測區(qū)域后不能被移動，也沒有辦法進行人為看管。

(3)節(jié)點的感知模型采用布爾感知模型，也就是說每個傳感器節(jié)點的通信半徑Rt和感知半徑Rs是固定的，它的通信范圍和感知范圍分別以傳感器節(jié)點為圓心，通信半徑為Rt和感知半徑為Rs的圓，并且滿足Rt≥2Rs。

(4)傳感器網(wǎng)絡中每個節(jié)點的時鐘達到秒級的時間同步。

(5)由于算法需要知道節(jié)點確切的地理位置信息，所以每個傳感器節(jié)點都需要安裝GPS或無向天線等定位裝置,并且每個節(jié)點的地理位置不能重合。

2 面向服務質(zhì)量的WSN節(jié)能調(diào)度算法

在無線傳感器網(wǎng)絡中，為了給用戶提供更好的服務質(zhì)量，需要保證數(shù)據(jù)傳輸?shù)目煽啃院蛯崟r性。由于傳感器能量高度受限，設(shè)計了一種面向服務質(zhì)量的WSN節(jié)能調(diào)度算法。算法分為無線傳感器網(wǎng)絡節(jié)能調(diào)度和基于服務質(zhì)量的路由兩部分。

2.1 無線傳感器網(wǎng)絡節(jié)能調(diào)度

2.1.1 節(jié)點狀態(tài)調(diào)度

節(jié)點的工作狀態(tài)分為監(jiān)聽狀態(tài)、睡眠狀態(tài)、工作狀態(tài)、加入狀態(tài)和退出狀態(tài)。所有節(jié)點初始狀態(tài)為監(jiān)聽狀態(tài)，每個節(jié)點隨機生成一個隨機數(shù)，如果這個隨機數(shù)小于預先設(shè)定的閥值(監(jiān)測區(qū)域總面積除以節(jié)點感知圓盤面積再除以節(jié)點總數(shù)目)，則轉(zhuǎn)入活躍狀態(tài)，否則進入睡眠狀態(tài)。活躍節(jié)點周期性地廣播Hello消息，告知自己的狀態(tài)和地理位置信息。

處于睡眠狀態(tài)的節(jié)點經(jīng)過一段隨機時間間隔Ts后，節(jié)點被喚醒，進入監(jiān)聽狀態(tài)，算法中設(shè)置了一個監(jiān)聽計時器T1，對監(jiān)聽過程進行計時。

節(jié)點在監(jiān)聽狀態(tài)下，對于收到三類消息(Hello、Withdraw或者Join消息)中的任何一類時，對是否滿足進入休眠狀態(tài)的條件進行判斷。若滿足休眠條件時，則轉(zhuǎn)入休眠狀態(tài)；若不滿足時，則設(shè)置計時器Tj。節(jié)點處于監(jiān)聽狀態(tài)時依據(jù)Tj設(shè)置，如果在計時器超時之前收到了其他相鄰節(jié)點的Join消息，也進入休眠狀態(tài)，并取消計時器Tj。處于監(jiān)聽狀態(tài)的節(jié)點在計時器超時的情況下，對外廣播一個Join消息后進入工作狀態(tài)。

處于工作狀態(tài)的節(jié)點如果收到Hello、Withdraw或者Join消息,檢查自己是否符合睡眠的條件，如果符合，進入退出狀態(tài)并啟動退出計時器，計時器溢出，廣播一個Withdraw消息，進入睡眠狀態(tài)，如果在計時器溢出之前收到了Hello或者Withdraw消息，撤銷計時器并返回工作狀態(tài)。

2.1.2 均衡分布網(wǎng)絡能量及延長網(wǎng)絡生存期

算法是按輪次進行的，這樣可以將整個網(wǎng)絡的能量平均分配到每個傳感器節(jié)點中，減少節(jié)點死亡數(shù)量，延長網(wǎng)絡生存時間。網(wǎng)絡按照網(wǎng)絡預先設(shè)定的輪次輪轉(zhuǎn)時間進行工作，當網(wǎng)絡中出現(xiàn)死亡節(jié)點，則重新開始新的一輪算法。

2.2 基于服務質(zhì)量的路由協(xié)議

在2.1中，主要解決了選擇部分節(jié)點工作，而其余節(jié)點狀態(tài)的調(diào)度，本節(jié)將主要解決工作節(jié)點怎樣將數(shù)據(jù)可靠傳輸?shù)絽R聚節(jié)點上，并且保證數(shù)據(jù)傳輸?shù)膶崟r性。

該算法主要由四部分組成：通信延遲估計、路由的選擇、反向壓力變更路由、節(jié)點失效的策略。

2.2.1 通信延遲估計

在通信延遲估計中，節(jié)點首先將數(shù)據(jù)分組并且給數(shù)據(jù)加上時間的標志，發(fā)送給下一跳節(jié)點，下一跳節(jié)點首先計算從收到數(shù)據(jù)包到返回ACK消息時間，并將它作為ACK消息的一部分返回給源節(jié)點；源節(jié)點收到ACK消息后，從總的收發(fā)的時間差中減去接收節(jié)點處理消息的時間，就是通信延遲時間。

2.2.2 路由的選擇

距離監(jiān)測區(qū)域更近的源節(jié)點的一跳鄰居節(jié)點為候選轉(zhuǎn)發(fā)節(jié)點集合(FCS，F(xiàn)orwarding Candidate Set)，源節(jié)點計算出FCS中節(jié)點的傳輸速率(節(jié)點間的距離除以兩個節(jié)點之間的通信延遲時間)。定義了一個傳輸速率的閥值，然后選擇出大于傳輸速率閥值的節(jié)點集，集合中節(jié)點的剩余能量越大，被選為下一跳數(shù)據(jù)傳輸節(jié)點的概率越大。

如果FCS集合中找不到大于傳輸速率閥值的節(jié)點，那么MAC層收集差錯信息，并且把源節(jié)點到FCS節(jié)點的傳輸差錯率報告給轉(zhuǎn)發(fā)比例器。若傳輸差錯率為0，則源節(jié)點將數(shù)據(jù)全部轉(zhuǎn)發(fā)到該節(jié)點。

2.2.3 反向壓力變更路由

如果網(wǎng)絡發(fā)生擁塞或有突發(fā)事件發(fā)生，并且阻礙了數(shù)據(jù)的正常傳輸時，節(jié)點需要對數(shù)據(jù)的轉(zhuǎn)發(fā)路由做出改變。此時應該向上一跳節(jié)點反應這種情況，那么上一跳節(jié)點接收到這樣的消息后，會重新在下一跳節(jié)點中做出選擇，這樣可以有效避免擁塞阻礙數(shù)據(jù)的傳輸。

源節(jié)點選擇多條路由傳輸數(shù)據(jù)，避免前方網(wǎng)絡擁塞嚴重，將數(shù)據(jù)分成若干份由不同的路徑傳輸，當主路由發(fā)生故障，則啟動其他路由進行傳輸，保證數(shù)據(jù)傳輸質(zhì)量。

2.2.4 節(jié)點失效的策略

如果有節(jié)點失效，那么網(wǎng)絡重新開始新的一輪工作節(jié)點的選擇，為了避免正在傳輸?shù)臄?shù)據(jù)丟失，那么正在傳輸數(shù)據(jù)的節(jié)點仍然為工作節(jié)點，不參加新的工作節(jié)點的選擇，發(fā)送Hello消息，參與鄰居節(jié)點是否冗余的判斷。

3 實驗結(jié)果與分析

為了評估面向服務質(zhì)量的WSN節(jié)能調(diào)度算法的性能，對該算法和其它算法進行了比較：

3.1 區(qū)域覆蓋率的比較

在100m×100m監(jiān)測區(qū)域內(nèi)隨機布撒無線傳感器節(jié)點，節(jié)點的感知半徑為10m、通信半徑為25m，在整個檢測區(qū)域中布撒的傳感器節(jié)點總數(shù)從100增加到1000，步長為100。圖1為面向服務質(zhì)量的WSN資源調(diào)度算法和CCP算法的覆蓋率對比圖，從圖1可以看出，兩種算法都能在給定的條件下達到99.9%以上的覆蓋率。

3.2 工作節(jié)點數(shù)的比較

仍然在100m×100m的監(jiān)測區(qū)域內(nèi)隨機布撒節(jié)點，感知半徑為10m、通信半徑為25m，傳感器節(jié)點數(shù)目從100增加到1000，步長為100。仿真比較在監(jiān)測區(qū)域中布撒相同數(shù)量的傳感器節(jié)點時，本文算法、CCP算法和PEAS算法保持網(wǎng)絡正常工作所需要的工作節(jié)點數(shù)。圖2為本文算法、CCP算法、PEAS算法的工作節(jié)點數(shù)對比圖。圖2仿真結(jié)果說明本文算法與CCP算法所需要的工作節(jié)點數(shù)目相當，但是其計算復雜度要優(yōu)于CCP算法。與PEAS算法比，工作節(jié)點數(shù)目明顯減少。

圖2 節(jié)點數(shù)VS工作節(jié)點數(shù)

3.3 網(wǎng)絡生存時間的比較

在100m×100m的監(jiān)測區(qū)域內(nèi)隨機布撒100個傳感器節(jié)點，傳感器的感知半徑為10m、通信半徑為25m，仿真比較了本文算法、CCP算法和PEAS算法隨著時間的增加網(wǎng)絡中剩余有效節(jié)點的數(shù)量變化。圖3比較了隨著時間的變化，面向服務質(zhì)量的WSN節(jié)能調(diào)度算法、CCP算法和PEAS算法剩余有效節(jié)點數(shù)量情況，仿真結(jié)果表明本文算法隨著時間的變化，剩余節(jié)點數(shù)量減少的最緩慢，其次是CCP算法，最后是PEAS算法。

3.4 算法可靠性分析

為了研究面向服務質(zhì)量的WSN節(jié)能調(diào)度算法、SAR協(xié)議和SPEED協(xié)議在不同傳輸速率下的可靠性，源節(jié)點的數(shù)據(jù)傳輸速率從5packets/s到100packets/s，兩個數(shù)據(jù)傳輸速率之間間隔為5packets/s。得到三種算法的丟包率曲線和傳輸延遲曲線，如圖4、圖5所示。圖4說明隨著數(shù)據(jù)傳輸速率的提高，本文算法比SAR協(xié)議和SPEED協(xié)議丟包率更低，數(shù)據(jù)傳輸更加可靠。當數(shù)據(jù)傳輸速率低時，傳輸時延接近0，隨著數(shù)據(jù)傳輸速率的提高，網(wǎng)絡可能發(fā)生擁塞，導致數(shù)據(jù)傳輸產(chǎn)生時延，圖5說明本文算法比SAR協(xié)議和SPEED協(xié)議隨著數(shù)據(jù)傳輸速率的提高產(chǎn)生的時延更短。

圖3 剩余有效節(jié)點隨時間變化曲線

圖4 數(shù)據(jù)傳輸速率VS丟包率

圖5 數(shù)據(jù)傳輸速率VS傳輸時延

4 結(jié)束語

首先提出了一種節(jié)點狀態(tài)調(diào)度算法，通過讓更多節(jié)點休眠和盡量減少通信消耗來節(jié)約能量。其次，提出了一種基于QoS的路由算法，由通信延遲估計、路由的選擇、反向壓力變更路由和節(jié)點X失效的策略四部分組成。最后，對本文提出的算法進行了仿真和實現(xiàn)，并和其他算法性能進行比較分析，結(jié)果表明算法能夠保證99.9%以上的覆蓋率，比其他算法需要更少的工作節(jié)點，網(wǎng)絡生存周期更長，數(shù)據(jù)丟包率更低，傳輸延遲更短。

[1]張紹軍.無線傳感器網(wǎng)絡技術(shù)及應用[M].北京：中國電力出版社，2010.

[2]汪鳳珠.無線傳感器網(wǎng)絡可靠路由協(xié)議的研究[D].北京：華北電力大學，2013.

[3]寇含.無線傳感器網(wǎng)絡QoS路由技術(shù)研究[D].南京：南京郵電大學，2012.

[4]Nidal Nasser,Lutful Karim,Tarik Taleb.Dynamic Multilevel Priority Packet Scheduling[J].IEEE Transactions On Communications 2013，4(4):1448-1459.

[5]Hyungsik Ju,Rui Zhang.Optimal Resource Allocation in Full-Duplex Wireless-Powered Communication Network[J].Transactions On Communications.，2014，9(10):3528-3540.

(責任編輯：馬金發(fā))

WSN Energy-efficient Scheduling Algorithm for Quality of Service

WANG Xu,LIANG Ying

(Shenyang Ligong University,Shenyang 110168,China)

To rationally use limited wireless sensor network(WSN)energy resources and to provide users with guaranteed network service the reasonable organization node is used for scheduling network nodes in working condition.And according to the way of data transmission by real-time routing algorithm,proposes a WSN energy-efficient scheduling algorithm for quality of service.Algorithms are divided into state of node scheduling and routing protocol based on the quality of service(QoS).And the simulation is carried out.The results show that the algorithm in the real-time and reliability of data transmission performance is superior.It has good scalability,and saves energy,prolongs the network life cycle.

wirless sensor network;energy-efficient;quality of service;the network life cycle

2014-12-18

王旭(1988—)，女，碩士研究生；通訊作者：梁英(1976—)，女，副教授，博士，研究方向：無線傳感器網(wǎng)絡嵌入式技術(shù).

1003-1251(2015)04-0066-05

TN921

A