劉 韜，李天瑞，譚 穎

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

0 引 言

根據(jù)數(shù)據(jù)匯報方式，無線傳感器網(wǎng)絡(luò)可以分為事件驅(qū)動型和周期匯報型兩類網(wǎng)絡(luò)［1］。在事件驅(qū)動型網(wǎng)絡(luò)中，節(jié)點很少產(chǎn)生數(shù)據(jù)，僅在待監(jiān)測的事件發(fā)生時才產(chǎn)生事件報告。而在周期匯報型網(wǎng)絡(luò)中，所有節(jié)點周期性地向匯聚節(jié)點報告采集到的信息。

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

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

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

1 網(wǎng)絡(luò)模型

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

2 MDR 協(xié)議及其優(yōu)化

數(shù)據(jù)包的時延是指從源節(jié)點產(chǎn)生數(shù)據(jù)包，一直到Sink接收該數(shù)據(jù)包所經(jīng)過的時間［6］。本文的研究對象為事件驅(qū)動型傳感器網(wǎng)絡(luò)，優(yōu)化時延性能是本協(xié)議所要解決的問題。由于節(jié)點極少發(fā)送數(shù)據(jù)，本文忽略不同路由的能耗差異對網(wǎng)絡(luò)性能的影響，也不考慮信號沖突與干擾。

2.1 MDR 協(xié)議概述

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

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

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

2.2 時延性能優(yōu)化

為了降低數(shù)據(jù)包從源節(jié)點發(fā)往Sink 的時延，需要從兩方面優(yōu)化MDR 協(xié)議:一是降低每跳路由的時延，二是減少數(shù)據(jù)包到達Sink 的路由跳數(shù)。

2.2.1 最小窗口時間

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

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

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

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

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

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

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

2.2.2 計算子區(qū)域Ui的面積

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

圖2 子區(qū)域Ui 的面積Fig 2 Size of subarea Ui

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

2.2.3 每跳平均傳輸距離

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

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

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

2.2.4 數(shù)據(jù)包在單跳路由上的時延

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

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

2.2.5 數(shù)據(jù)包發(fā)往Sink 的總時延

為了判斷子區(qū)域的數(shù)量k 對總時延的影響，使用算法1來計算任一節(jié)點把數(shù)據(jù)包發(fā)往Sink 的平均總時延dtotal。該節(jié)點距離Sink 的距離為D。

算法1:計算數(shù)據(jù)包發(fā)往Sink 的總時延

1)dtotal=0;

2)while D ＞r

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

8)end while

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

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

在k 的取值范圍內(nèi)，分別使用算法1 計算k 取不同值時數(shù)據(jù)包發(fā)往Sink 的總時延，從而獲得使得總時延最小時的k 值。

2.3 完善MDR 協(xié)議

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

網(wǎng)絡(luò)開始運行后，當某節(jié)點探測到事件發(fā)生時，根據(jù)MDR 協(xié)議，發(fā)送RTS 消息，并捎帶相應的k 值、節(jié)點的位置信息，以及窗口時間長度T;其它節(jié)點收到RTS 消息后，根據(jù)相關(guān)信息計算自己所對應的分區(qū)，然后按MDR 協(xié)議響應RTS 消息。

3 實 驗

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

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

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

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

4 結(jié) 論

圖5 網(wǎng)絡(luò)時延性能比較Fig 5 Comparison of delay performances of networks

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

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

［2］ 王辛果，張信明，陳國良.時延受限且能量高效的無線傳感器網(wǎng)絡(luò)跨層路由［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］ 梁慶偉，姚道遠，鞏思亮.一種保障時延能量高效的無線傳感器網(wǎng)絡(luò)路由協(xié)議［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.