事件驅動型無線傳感器網絡最小時延路由協議*

劉 韜，李天瑞，譚 穎

(1.西南交通大學 信息科學與技術學院，四川 成都610031;2.西南民族大學 計算機科學與技術學院，四川 成都610041)

0 引 言

根據數據匯報方式，無線傳感器網絡可以分為事件驅動型和周期匯報型兩類網絡［1］。在事件驅動型網絡中，節點很少產生數據，僅在待監測的事件發生時才產生事件報告。而在周期匯報型網絡中，所有節點周期性地向匯聚節點報告采集到的信息。

兩類網絡對性能的需求存在較大的差異:周期匯報型網絡由于需要傳輸的數據量大，要求盡可能降低節點的能耗，對時延性能的要求相對不高;事件驅動型網絡中節點的報告需要及時地被傳輸到匯聚節點，否則，可能會產生災難性的后果，所以，這種網絡對時延性能要求較高，而該型網絡由于數據量少，對節約能耗的要求不高。現有的絕大部分針對路由的研究都著眼于如何提高網絡的能量利用效率，降低和平衡節點的能耗。顯然，此類研究并沒有考慮數據在路由過程中的時延問題，其成果并不適用于事件驅動型傳感器網絡。

文獻［2］則主要關注事件驅動型網絡，提出了一種時延受限且能量高效的跨層路由協議，該協議雖然將端到端的時延控制在一定的范圍內，但并沒有優化時延。文獻［3］提出了一種能量多路徑路由機制，同時優化能耗與時延性能，但此機制開銷大，算法復雜，維護困難。PRTR協議［4］則基于節點梯度與緩沖隊列占空比建成的復合勢場來保證數據具有較小的網絡時延，但該協議會過度使用最短路徑上的節點，從而降低了網絡壽命。文獻［5］在文獻［4］的基礎上提出了一種保障時延、能量高效的路由(DGEER)協議，該協議將數據分為時延敏感數據和非時延敏感數據，分別使用不同的路徑發送到匯聚節點。該協議緩解了最短路徑的過度使用問題，但是它要求事先確定每個節點到達匯聚節點的最短路徑，這顯然增加了網絡開銷。文獻［6］使用RTS/CTS(請求發送/允許發送)消息機制建立節點路由，減少了節點計算路由的開銷，但該協議并沒有對時延性能進行優化。

針對現有研究的不足，本文提出了一種專用于事件驅動型無線傳感器網絡的最小時延路由(minimun delay routing，MDR)協議。MDR 協議利用RTS/CTS 消息機制建立路由，并最小化數據包發到匯聚節點的時延。該協議的計算開銷小，維護簡單。

1 網絡模型

整個網絡由一個匯聚節點(Sink)和多個傳感器節點組成，節點均勻分布于監控區域內，分布密度為ρ;每個節點可以通過GPS 裝置或定位算法獲得自身的地理位置信息;所有傳感器節點平時不發送數據，只有當所監測的事件發生時才向Sink 發送報告;所有節點具有相同的最大無線傳輸半徑r。

2 MDR 協議及其優化

數據包的時延是指從源節點產生數據包，一直到Sink接收該數據包所經過的時間［6］。本文的研究對象為事件驅動型傳感器網絡，優化時延性能是本協議所要解決的問題。由于節點極少發送數據，本文忽略不同路由的能耗差異對網絡性能的影響，也不考慮信號沖突與干擾。

2.1 MDR 協議概述

MDR 協議中，若網絡中任一節點A 有感應數據包要發送，它先廣播一個RTS 消息。本文把既位于節點A 的通信范圍，又將A 離Sink 距離近的區域稱之為節點A 的下一跳可達區域，如圖1 的陰影區域所示。只有位于節點A 的下一跳可達區域的節點，接收到來自節點A 的RTS 消息才準備回復CTS。

圖1 源節點下一跳可達區域與目的節點競爭機制圖Fig 1 Reachable area of source node next hop and competition mechanism of destination

為了使節點每跳路由能夠前進盡可能遠的距離，把節點的下一跳可達區域按照到Sink 的距離劃分為k(k≥2)個長度為d 的子區域，即Ui，i=1，...，k，如圖1 所示，并給每個子區域分配一個后退窗口，窗口時間長度為T。位于子區域Ui的節點必須先等待k-i 個窗口時間，再在［0，T］時間段內的任一時間發送CTS 消息，即只能選擇［(k-i)T，(k-i)T+T］時間段內的時間發送CTS 消息。該過程將節點A 的鄰居節點按地理位置劃分為回復CTS 消息的多個優先級組，即先由最外層子區域的節點在相應的時間段內發送CTS 消息，其余子區域的節點等待;若最外層子區域沒有節點發送CTS 消息，再由次外層子區域的節點發送CTS 消息;…，以此類推，直至第1 層。其中，任一節點發送CTS 消息，其余節點偵聽到此CTS 消息后取消自己發送CTS，競爭過程結束，而成功發送CTS 消息的節點成為節點A 的下一跳目的節點。

2.2 時延性能優化

為了降低數據包從源節點發往Sink 的時延，需要從兩方面優化MDR 協議:一是降低每跳路由的時延，二是減少數據包到達Sink 的路由跳數。

2.2.1 最小窗口時間

根據MDR 協議，縮短窗口時間T 可以顯著降低每跳路由的時延。但是，若窗口時間長度過短，會增加因多個節點同時發送CTS 消息而沖突的概率。

位于子區域Ui的節點選擇回復CTS 消息的時間為t，顯然，t 在［(k-i)T，(k-i)T+T］上服從均勻分布，其概率密度為f(t)=1/T。

假設子區域Ui中的某一節點在時刻t 最先發出CTS消息，子區域Ui中的其它節點至少要經過τ 秒才能偵測到此CTS 消息，并取消自己發送CTS 消息。顯然，子區域Ui中的其它節點原本發送CTS 消息的時間要安排在(t+τ，(k-i)T+T］時間段內才可以避免沖突。于是，子區域Ui中無沖突發生的概率p 為

其中，ni為子區域Ui中的節點數量，可以通過pSi計算，Si為子區域Ui的面積，其計算方法在下一小節闡述。因為子區域Ui中有ni個節點，那么該子區域不沖突的總概率P 為nip，結合公式(1)和f(t)=1/T，可得

假設不沖突概率的門限值為l，即要求滿足P≥l，根據公式(2)可得

根據公式(3)，可以獲得滿足低沖突概率所需的最小后退窗口時間長度。如果子區域Ui中的節點數量較多，τ 與T 相差較大趨近于0，進而根據公式(3)得到

由于節點的下一跳可達區域的每個子區域所包含的節點數量不同，所以，根據式(3)或式(4)得出的每個子區域所需的最小T 的值不同。為簡化，把其中最大的T 值設置為節點的后退窗口時間長度。

2.2.2 計算子區域Ui的面積

如圖2 所示，D 為節點A 與Sink 的距離，陰影區域為以Sink 為圓心，以D-x 與D-x-dx 為半徑所構成的兩個圓與節點A 的傳輸范圍所圍成的圖形，dx 是自變量x 的微分，該陰影區域的面積S(x)為

圖2 子區域Ui 的面積Fig 2 Size of subarea Ui

通過公式(6)與積分，可以獲得Ui的面積

2.2.3 每跳平均傳輸距離

要降低數據包到達Sink 的時延，還要減少數據包經多跳路由到達Sink 的過程中所經歷的跳數，即提高數據包在每跳路由的前進距離。

假設任一節點A 發送RTS 消息，dist 為節點A 的數據包在單跳路由中朝向Sink 的前進距離，若節點A 的子區域Ui中的鄰居節點首先發送CTS 消息回復，當寬度d 較小時，可以認為數據包在此跳路由的平均前進距離為(i-0.5)d。

根據文獻［7］，因節點均勻分布，所以，節點的部署服從泊松分布，于是，節點在面積為S 的區域內沒有節點分布的概率為e-ρS。若節點A 的下一跳可達區域劃分為k 個子區域，根據MDR 協議，節點A 的數據包此跳前進距離dist的期望可計算為

2.2.4 數據包在單跳路由上的時延

這里使用delay 表示節點在單跳路由上的平均時延，包括節點發送RTS 消息花費的時間、等待CTS 消息的時間、接收CTS 和發送數據包所花費的時間。另外，如果節點先等待k-i 個窗口時間后，子區域Ui中有節點回復CTS。因回復CTS 消息的時間在［(k-i)T，(k-i)T+T］上服從均勻分布，則平均回復時間可以認為是(k-i)T +0.5T，那么，單跳路由上時延的期望可計算為

其中，tsend為節點發送RTS 消息、接收CTS 消息和發送感應數據包所花費的時間，它可以通過節點的數據發送速率和數據包長度來計算。

2.2.5 數據包發往Sink 的總時延

為了判斷子區域的數量k 對總時延的影響，使用算法1來計算任一節點把數據包發往Sink 的平均總時延dtotal。該節點距離Sink 的距離為D。

算法1:計算數據包發往Sink 的總時延

1)dtotal=0;

2)while D ＞r

4) 通過式(3)或式(4)獲得窗口時間長度T;

8)end while

9) dtotal=dtotal+最后一跳的時延。

其中，最后一跳的時延指的是最后一跳節點直接和Sink 進行通信的時延，此時節點無需發送RTS 消息，而是直接把數據包發給Sink。

在k 的取值范圍內，分別使用算法1 計算k 取不同值時數據包發往Sink 的總時延，從而獲得使得總時延最小時的k 值。

2.3 完善MDR 協議

網絡初始化時，每個節點將自身的位置信息發給Sink。Sink 根據該位置信息計算出該節點與Sink 的距離D，然后使用算法1 獲得使得該節點的數據包發往Sink 的總時延最小時的k 值和窗口時間長度T，并把此k 和T 值發消息通知給該節點。

網絡開始運行后，當某節點探測到事件發生時，根據MDR 協議，發送RTS 消息，并捎帶相應的k 值、節點的位置信息，以及窗口時間長度T;其它節點收到RTS 消息后，根據相關信息計算自己所對應的分區，然后按MDR 協議響應RTS 消息。

3 實 驗

利用OPNET 作為仿真平臺對MDR 協議的時延性能進行評估。如無特別指定，實驗中的參數設置如下:D=200 m，r=20 m，ρ=0.05，l=0.005，τ=0.001，數據包的長度為80 bits，消息包的長度均為20 bits，節點的數據發送速率為20 kB/s。

圖3 反映了網絡采用MDR 協議，在參數k 的不同取值下，數據包從源節點發送到Sink 的總時延，從圖3 可以看出:當k=6 時，時延最小。分析結果和模擬結果基本保持一致，從而證明了分析的正確性。圖4 反映了在不同的參數k 下，數據包從源節點發送到Sink 所經歷的路由總跳數。從圖4 中可以看出:當k 變大時，數據包到達Sink 所經歷的跳數不斷減少，這是由于k 變大時，距離源節點遠的節點會先回復CTS，這樣，數據包在每跳路由前進距離變遠，降低了總跳數。圖5 反映了不同D 值下網絡分別采用MDR 與PRTR［4］，XLP［6］三種協議時數據包發往Sink 的總時延。從圖5 可以看出:網絡采用MDR 協議時，時延最小。

圖3 不同k 值下數據包到達Sink 的時延Fig 3 Time delay of data packets arriving at sink with different k value

圖4 不同k 值下數據包到達Sink 的跳數Fig 4 Number of hops of data packets arriving at Sink with different k value

4 結 論

圖5 網絡時延性能比較Fig 5 Comparison of delay performances of networks

針對事件驅動型傳感器網絡，提出了一種MDR 協議。該協議利用了RTS/CTS 消息機制建立路由，通過控制節點的下一跳可達區域的子區域的數量和對應的窗口時間長度來優化網絡的時延性能。實驗結果表明:MDR 協議有效提高了網絡的時延性能。

［1］ 王辛果，張信明，陳國良.時延受限且能量高效的無線傳感器網絡跨層路由［J］.軟件學報，2011，22(7):1626-1640.

［2］ 王辛果，張信明，陳國良.時延受限且能量高效的無線傳感器網絡跨層路由［J］.軟件學報，2011，22(7):1626-1640.

［3］ Pothuri K，Sarangan V，Thomas J P.Delay-constrained，energyefficient routing in wireless sensor networks through topology control［C］∥Proceedings of the 2006 IEEE International Conferance，Piscataway，NJ，USA:IEEE，2006:35-41.

［4］ Xu Yingsheng，Ren Fengyuan，He Tao.Building a potential field to provide real-time transmission in wireless sensor networks［C］∥Proceedings of the 13th ACM International Conference on Modeling，Analysis and Simulation of Wireless and Mobile Systems，New York，USA:ACM，2010:403-410.

［5］ 梁慶偉，姚道遠，鞏思亮.一種保障時延能量高效的無線傳感器網絡路由協議［J］.西安交通大學學報，2012，46(6):48-52.

［6］ Mehmet C Vuran，Ian F Akyildiz.XLP:A cross-layer protocol for efficient communication in wireless sensor networks［J］.IEEE Trans on Mobile Computing，2010，9(11):1578-1591.

［7］ Wang Y，Wang X D，Xie B，et al.Intrusion detection in homogeneous and heterogeneous wireless sensor networks［J］.IEEE Trans on Mobile Computing，2008，7(6):698-711.