無線傳感器網絡中雙信道無信標實時路由協議

黃超

（廣東技術師范學院計算機科學學院，廣州　510665）

無線傳感器網絡中雙信道無信標實時路由協議

黃超

（廣東技術師范學院計算機科學學院，廣州510665）

0　引言

無線傳感器網絡是由部署在監測區域內大量的傳感器節點通過無線通信方式形成的一個多跳的自組織網絡系統，可廣泛應用在環境監測、國防軍事、醫療健康以及搶險救災等領域［1］。某些事件驅動的應用對無線傳感器網絡數據傳輸的實時性提出了較高要求，例如在森林防火等事件驅動應用中，火警事件的發生會使得網絡中感知數據將瞬間劇增，產生的網絡擁塞和沖突會增加感知信息的傳輸時延，導致異常高溫信息無法實時有效地傳送到監測中心。由此可見，事件驅動等高負載網絡環境給無線傳感器網絡的實時性研究提出了更高的挑戰。

現有的實時路由協議［2］主要采用傳統的地理路由模式，使用周期性信標廣播來建立鄰居節點的位置、能量和延遲等相關信息的鄰居表。盡管信標廣播能夠獲取鄰居節點的準確信息，但也帶來一些不足：①能耗較高：額外的信標廣播會耗費更多的能量；②通信開銷較大：所有節點都需要定期廣播信標，增加了網絡通信開銷；③鄰居表信息利用率低：路由選擇中往往只需從鄰居表中選擇一個或極少數節點參與路由轉發，鄰居表信息的利用率很低，而且保存大量未參與路由轉發的鄰居信息還會增加節點存儲開銷；④不適合動態性網絡：當網絡拓撲變化較強時，鄰居表的準確度將降低，而為維護鄰居表信息的準確性，節點需要更頻繁地廣播信標，增加能量消耗和網絡延遲；⑤高負載網絡中信標廣播會加劇網絡沖突；⑥網絡節點大規模密集部署時，信標方式的上述不足將變得更加嚴重。因此，現有實時路由協議通常以犧牲能量來換取實時性保證，這與能量高效的首要設計目標存在直接矛盾。

為克服傳統地理路由因鄰居表信息不準確而導致能耗高，代價大的問題，研究人員提出了基于競爭的無信標轉發［3］，它的基本思想是發送節點廣播競爭請求，鄰居節點接收到請求后根據自身狀態來決定參與競爭的等待響應時間，只有等待響應時間最短的鄰居競爭成為轉發節點。基于競爭的無信標轉發方式可以在沒有鄰居節點先驗信息情況下，讓節點以能耗低、開銷小的方式選出下跳接收節點。在競爭選擇轉發節點的過程中，無信標轉發不需要任何信標就可以獲取所選定鄰居的信息，如果能夠將每次競爭所選擇的節點信息保存到鄰接表，就可以利用這些局部信息輔助實時路由決策。由此可見，通過無信標轉發建立鄰接表的方式可以完全克服信標方式能耗高、代價大的缺點。

基于上述想法，本文提出了雙信道無信標實時路由協議 DBRR （Dual-channel Beaconless Real-time Routing），它的基本思想是在數據轉發的初始階段（即源節點第一個DATA包的發送），每個節點通過競爭機制選擇其下跳轉發節點，同時將已選中節點的信息保存在鄰居表中；在后續的路由過程中，節點根據鄰居表中是否有滿足實時性要求的鄰居節點，采用無信標轉發和鄰居表相結合的轉發策略，使用單跳間的速率約束和延遲約束來滿足端對端實時性要求。DBRR只有在鄰居表中沒有節點滿足實時性要求時才發起競爭，選擇新鄰居作為轉發節點并加入鄰居表中，具有能耗低、開銷小、鄰居表信息利用率高等優點。此外，為緩解高負載網絡擁塞和沖突，DBRR采用擇數據信息和控制信息隔離傳輸的雙信道并行傳輸方式，避免控制信息和數據信息的沖突，不僅可以節約能量，還可以減少網絡數據的傳輸延遲，提高傳遞成功率，更好地滿足高負載網絡下的實時性需要。

1　相關工作

實時性是當前無線傳感器網絡服務質量究的重要內容。SPEED［4］采用無狀態非確定地理轉發的SNGF機制，優先選擇滿足速率要求且負載較輕的鄰居節點作為下跳轉發節點，為端對端路由提供軟實時保證。MMSPEED［5］對SPEED進行了拓展，為多種業務提供區分服務支持以及實時性和可靠性保證。QGR［6］采用分級排隊模型為圖像傳感器網絡中周期性低帶寬和事件驅動高帶寬兩類數據分配不同級別，以高優先級別保證事件驅動的圖像信息傳輸的實時性和能量高效。PRTR［7］利用多路徑傳輸方式緩解網絡擁塞，為實時數據流提供更好的實時性傳輸。

無信標轉發在能量效率和通信代價方面有較好優勢。IGF［8］采用lazy binding思想來處理網絡動態變化，它采用DRA扇形轉發區域，候選轉發節點根據自身離目標節點的增進距離以及剩余能量來決定競爭的等待響應時間。OGF［9］針對拓撲變化不劇烈的網絡，提出了競爭機制和鄰居表相結合的按需轉發策略，但OGF鄰居表只保存一個轉發節點信息，沒有充分利用每次選出的轉發節點信息，也沒有提供實時性保證。CBRR［10］基于包接收率模型，充分利用無信標轉發和協作通信的優勢，完全避免冗余探測包的使用，并通過等待響應時間設定、協作節點概率保證以及冗余數據包發送等方式實現單跳數據傳輸的可靠性保證。

IEEE 802.11［11］等單信道協議大多使用RTS/CTS握手機制來解決隱終端問題［12］，然而僅用握手機制不僅不能消除所有沖突，還會引起暴露終端問題，導致信道利用率下降。為克服單信道的不足，研究人員提出了雙信道MAC協議來解決隱終端問題。DBTMA［13］通過BTs和BTr兩個忙音信號 （Busy Tone）將收發狀態通知鄰節點，有效地減輕數據包的沖突。DUCHA［14］采用雙信道和忙音解決了包括隱終端和暴露終端在內的若干問題，徹底避免數據包的沖突和重發；CORA［15］利用雙信道通信模式降低信道競爭過程中數據碰撞和多播抑制概率；再使用最大感染球策略壓縮蟻群尋路范圍，降低網絡尋路能耗。

2　雙信道無信標實時路由協議（DBRR）

DBRR采用無信標轉發和鄰居表相結合的轉發策略，使用單跳間的速率約束和延遲約束來滿足端對端的實時性要求。DBRR將無線信道劃分為控制子信道和數據子信道，采用ERTS（DRTS）-ECTS-DATA-ACK握手機制選擇轉發節點，控制子信道用于傳遞ERTS、DRTS和ECTS等控制幀，其中ERTS是在RTS的基礎上增加了當前轉發節點和目標節點的位置信息以及所要求的延遲約束，DRTS在ERTS的基礎上再增加了有效鄰居節點ID號，ECTS是在CTS的基礎上增加了發送CTS節點的位置信息；數據子信道傳輸DATA和ACK等數據幀。DBRR通過雙信道傳輸策略，不僅可以避免控制幀和數據幀的沖突，還可以并行傳送控制幀和數據幀，減少延遲。

源節點和目標節點分別用S和D表示，d（i，j）表示節點i和j之間的歐氏距離，表示節點i和j之間的單跳延遲，Deadline（D）為目標節點D對數據的截止時刻，Rc為節點的通信半徑。

鄰居節點集NSi（Neighbor Set）：位于節點i通信范圍內的節點集，即滿足NS=｛j|d（i，j）≤R｝。

實時性速率SpeediD：滿足實時性約束的速率，為節點i與目標節點D間的距離與當前截止剩余時間的比值，即SpeediD=d（i，D）/（Deadline（D）-Tnow），其中Tnow為當前時刻。

候選轉發節點集FCSi：節點i的候選競爭節點集中滿足實時性速率要求的節點集，即：

估計跳數HopiD：節點i到目標節點D的估計跳數，為節點i和目標節點D的距離與通信半徑之比，即HopiD=d（i，D）/Rc。

延遲約束：無信標轉發采用延遲約束來決定候選競爭節點能否參與競爭。若候選競爭節點的鄰居表中存在一跳延遲不小于實時性單跳延遲DelayiD的鄰居節點，則該候選節點可以參與競爭；否則，該候選節點將不能參與競爭。

此外，本文做出以下合理假設：①節點位置已知；②節點分配有唯一 ID；③節點裝配有忙音（Busy Tone）；④節點的通信半徑和初始能量均相同。

雙信道并行傳輸的基本思想是：節點在數據子信道接收上跳節點發送的DATA包時，同時在控制信道中廣播ERTS/DRTS選擇新的下跳轉發節點。

在IEEE 802.11中，RTS、CTS和ACK的幀長度分別為44bytes、38 bytes和38 bytes，假設DATA包的大小為data_size，控制子信道帶寬為bw_control，數據子信道的帶寬為bw_data。對于非源節點，雙信道經過一輪RTS-CTS-DATA-ACK握手機制所需的時間T為：

由此可見，當控制信道和數據信道的帶寬固定時，DATA包的大小是影響T的關鍵因素。假設總帶寬為2Mbps，控制子信道帶寬為0.4Mbps，數據子信道為1.6Mbps，則當DATA包大于300bytes時，數據信道傳送DATA和ACK`的時間將大于控制信道中RTS和CTS的傳送時間。以此可見，對于DATA較大的傳送，雙信道并行傳輸可以減少延時。

DBRR的轉發策略與當前發送節點的鄰接表密切相關：

（1）直接轉發方式：當鄰接表中有滿足速率約束的有效鄰居節點時，發送節點廣播發送DRTS幀，只有與DRTS中有效鄰居節點ID號相同的節點成為轉發節點并在SIFS時間后發送ECTS；發送節點收到ECTS后，在數據子信道中向轉發節點發送DATA包并發送忙音信號抑制其它候選節點參與轉發競爭；同時轉發節點在控制子信道中發起它的新一輪轉發節點選擇。

（2）無信標轉發方式：當鄰接表中沒有有滿足速率約束的有效鄰居節點時，將采用延遲約束保證實時性。發送節點廣播發送ERTS幀，如果候選競爭節點的鄰接表為空，則該候選競爭節點將在Tlong時間后發送ECTS；若候選競爭節點的鄰接表中存在滿足延遲約束的鄰居節點時，該候選競爭節點將在Tshort時間后發送ECTS；否則表明無滿足實時性要求的競爭節點，丟棄DATA包。Tlong和Tshort的計算參照2.4。

競爭優先級函數是基于競爭無信標轉發策略的關鍵，它決定了鄰居節點的等待響應時間。優先級函數中的參數可根據應用的需要來設定，為滿足實時性和能量高效的要求，本文綜合考慮排隊延遲、傳播延遲和能量，建立增進距離、剩余能量、隊列中排隊包的數量以及隨機數為參數的競爭函數：

其中pi為鄰居節點的優先級；di為當前轉發節點到目標節點的歐氏距離與節點與目標節點的歐氏距離之差；Rc為節點的通信半徑；Ei和Et分別為節點的當前剩余能量和初始能量；qi和Qt分別為當前隊列中排隊包的數量和隊列總大小；ri為0～1間的隨機數；α、β、γ和η分別為距離、能量、隊列和隨機數的權值并且滿足α+β+γ+η=1。

無信標轉發策略中的短等待時間和長等待時間設置如下：

其中SIFS的值由802.11 DCF中定義為10μs。由（3）和（4）知，短等待響應時間Tshort不小于長等待響應時間Tlong。

本文采用與SPEED相似的延遲估計方法，由當前轉發節點記錄包進入隊列的時間Tarrive和接收到ACK的時間TACK，當前單跳延遲即為TACK和Tarrive之差，另外單跳延遲還需要綜合考慮歷史單跳延遲的影響，因此單跳延遲定義如下：

鄰居表是由節點在競爭轉發資格的過程中動態建立，它用于保存每次競爭所選擇的鄰居節點信息。在數據轉發的初始階段，所有節點的鄰居表都為空，在后續的轉發過程中，只有節點的鄰居表中沒有滿足速率約束的鄰居時，才發起競爭選擇新的轉發節點，否則鄰居表的大小保持不變。因此，鄰居表的大小只與節點發起競爭的次數有關，所需的存儲開銷較小。

表1　一跳鄰居表結構

一跳鄰居表的結構如表1所示：其中Neighbor ID 和Neighbor Position的信息由下跳轉發節點響應的ECTS稍帶，節點間的一跳延遲OneHop Delay由當前轉發節點依照2.5獲得，Count記錄該鄰居已成為下跳轉發節點的次數。

3　實驗及結果

為驗證協議在網絡高負載環境下的性能，本文在J-Sim［16］平臺上實現了DBRR和SPEED協議，J-Sim是由Java語言開發的一種開源的，基于組件的網絡仿真環境。協議的評價性能指標包括：①傳遞成功率（Delivery Ratio）：指sink成功接收數據包的數量與源節點發送數據包總數的比值；②平均端到端延遲（Average End-To-End Delay）：指數據包從源節點傳遞到sink所平均耗費的時間；③平均能耗 （Average Consumption Energy）：指成功傳遞一個數據包所耗費的能量；④總通信代價 （Total Communication Cost）：指發送RTS/ ERTS/DRTS、CTS/ECTS、DATA、ACK以及Beacon等各類幀的總數量。

仿真策略是在一個200×200網絡中部署200個節點，從網絡右邊任選兩個節點作為目標節點，左邊任取4個節點作為源節點；數據流采用CBR（Constant Bit Rate），無線信道總帶寬2M，其中控制子信道為0.4M，數據子信道1.6M；節點初始能量100J，它的發送能耗、接收能耗和空閑能耗分別為 660mW、395mW 和35mW。考察協議在高負載網絡中的性能，包括數據包產生速率和數據包大兩組實驗，其中數據包產生速率實驗的DATA包大小為512bytes，數據包大小實驗的CBR設定為20packets/s。

圖1考察了DBRR和SPEED在數據包產生速率場景的性能。圖1a顯示，當CBR小于15時SPEED的成功率仍可保持90%以上，但當CBR繼續增大時它的成功率將快速降低，當CBR為50時成功率已低于10%。這主要是因為網絡沖突引起節點包的重發次數增多和網絡擁塞，從而導致丟包率增加；相反，DBRR采用雙信道傳輸，可以減少控制幀與數據幀的沖突，緩解網絡擁塞，當CBR為40時，依然保持近100%的成功率，盡管CBR繼續增大是成功率有所降低，但CBR 為50時成功率仍然接近70%。CBR引起的網絡擁塞對端對端延遲的影響也很大，如圖1b所示，SPEED的延遲在CBR高于20時快速增加，而DBRR的延遲盡管在CBR大于40時也增長較快，但明顯低于SPEED；另外，DBRR的轉發策略也對延遲的減少起到作用。由圖1c知，當CBR低于20時，DBRR的平均能耗高于SPEED，原因在于DBRR的兩個子信道都始終處于工作狀態，所以能耗較大；當CBR高于20時，SPEED的成功率快速導致其平均能耗低于DBRR。值得注意的是，兩種協議的平均能耗都呈先下降然后上升，是因為CBR較小時，網絡負載較輕，節點休閑所耗費的能量占總耗能的比重也高，所以平均能耗較低；而當CBR增大時，節點傳輸所耗費的能量占總耗能的比重增加，平均能耗也提高；當CBR較大時，會加劇網絡擁塞，不僅耗能更多的能量，還會引起成功率降低，所以此時平均能耗又降低。如圖1d所示，由于DBRR始終廣播DRTS 或ERTS選擇轉發節點，所以在CBR較低時，它的通信代價高于SPEED；但當CBR較大時，網絡沖突增大會加劇網絡擁塞，SPEED利鄰居表單播發送的方式可能失效，需要重新廣播RTS選擇轉發節點，所以此時SPEED的通信代價高于DBRR；當CBR高于40時，SPEED低于30%的的成功率表明節點在廣播RTS后無法接收到CTS響應的概率增加，從而導致通信代價降低。

圖1　數據包產生速率實驗性能比較

圖2　數據包大小實驗性能比較

圖2考察了DBRR和SPEED在數據包大小場景的性能。圖2a顯示，數據包的大小對DBRR的影響較小，即使數據包為1000bytes時，它的成功率仍然大于80%，原因在于DBRR采用雙信道傳輸機制，使兩個子信道中幀的沖突概率大大降低；數據包大小對SPEED的影響較大，當數據包大于500bytes時，SPEED的成功率快速下降，原因在于數據包越大，它與RTS、CTS和ACK等幀沖突的概率越高，導致丟包率升高以及延遲和能耗的增大。而圖2b顯示，當數據包小于300bytes時，DBRR的延遲高于SPEED，這與3.4.1中的分析相符合；但當數據包大于300bytes時，DBRR的延遲低于SPEED，這也是因為SPEED中數據幀與其他信息幀沖突高于DBRR。如圖11c所示，當數據包小于300bytes時，DBRR的平均能耗在高于于SPEED，原因在于DBRR的兩個信道都始終處于工作狀態，所以能耗較大；但隨著數據包大小的增大，SPEED的沖突加劇而使其平均能耗明顯高于DBRR。圖2d顯示DBRR的通信代價高于SPEED，主要是因為始終廣播DRTS或ERTS來選擇轉發節點。

上述仿真實驗表明，DBRR的傳遞成功率和延遲要明顯優于SPEED，而隨著CBR和數據包大小的增加，DBRR在平均能耗和通信代價的性能也要好于SPEED，表明雙信道傳輸機制對緩解因沖突引起的網絡擁塞起到了有效的作用。

4　結語

本文為高負載無線傳感器網絡環境提出了一種雙信道無信標實時路由協議DBRR。DBRR利用無信標轉發方式建立節點鄰接表，并根據鄰接表的有效性采用速率約束和單跳延遲約束來保證數據傳輸的實時性。此外，DBRR利用雙信道并行傳輸，完全避免控制幀和數據幀的沖突，可以有效緩提高的網絡的能量效率和傳輸性能。

［1］I.Akyildiz，W.Su，E.Cayirci，Y.Sankarasubramaniam.Wireless sensor networks：A survey.Computer Networks，2002，3：393-422.

［

2］Y.Li，C.Chen，Y.Song，Z.Wang.Real-time qos support in wireless sensor networks：a survey.In Proceedings of seventh IFAC International Conference on Fieldbuses and nETworks in industrial and embedded systems，2007，11：373-380.

［3］J.Sanchez，P.Ruiz，R.Marin-Perez.Beacon-less geographic routing made practical：challenges，design guidelines，and protocols.Real-Time Systems，2009，47：85-91.

［4］T.He，J.Stankovic，C.Lu，T.Abdelzaher.A spatiotemporal communication protocol for wireless sensor networks.IEEE Transactions on Parallel Distributed Systems，2005，16：995-1006.

［5］E.Felemban，C.Lee，Ekici E.MMSPEED：multipath Multi-SPEED protocol for QoS guarantee of reliability and.Timeliness in wireless sensor networks.Mobile Computing，IEEE Transactions on Mobile Computing，2006，5：738-754.

［6］L.Savidge et al.QoS-based geographic routing for event-driven image sensor networks.In Broadband Networks 2005，2nd International Conference on，2005.

［7］Y.Xu，F.Ren，T.He.Real-time routing in wireless sensor networks：A potential field approach.ACM Transactions on Sensor Networks，vol.9：Article No.35，2013.

［8］T.He et al.，Robust and timely communication over highly dynamic sensor networks.Real-Time Systems，2007，37：261-289.

［9］D.Cheng，P.Varshney.On-demand geographic forwarding for data delivery in wireless sensor networks.Computer Communications，2007，30：2954-2967.

［10］黃超，王國利.無線傳感器網絡協作無信標可靠路由協議［J］.中山大學學報自然科學版，2013，52：39-44.

［11］IEEE.NSI/IEEE Std.802.11，1999 Edn.Part 11：wireless LANMedium Access Control（MAC）and Physical Layer（PHY）specifications.IEEE，1999.

［12］K.Kosek-Szott.A survey of mac layer solutions to the hidden node problem in ad-hoc networks.Ad Hoc Networks，2012，10：635-660.

［13］Z.Haas，J.Deng.Dual busy tone multiple access（dbtma）-a multipleaccess control scheme for ad hoc networks.IEEE Transactions on Communications，2002，50：975-985.

［14］H.Zhai，J.Wang，Y.Fang.DUCHA：A new dual-channel MAC protocol for multihop Ad hoc networks.IEEE Transaction on Wireless Communications，2006，5：3224-3233.

［15］劉逵，劉三陽，焦合華.一種蟻群策略的雙信道傳感器網絡路由算法［J］.西安電子科技大學學報（自然科學版），2013，40：71-77.

［16］J-Sim simulator：http：//j-sim.cs.uiuc.edu/index.html.

Wireless Sensor Network；Real-Time Routing；Dual-Channel；Beaconless Forwarding

Dual-channel Beaconless Real-time Routing Protocol for Wireless Sensor Networks

HUANG Chao
（School of Computer Science，Guangdong Polytechnic Normal University，Guangzhou 501665）

1007-1423（2015）22-0011-07

10.3969/j.issn.1007-1423.2015.22.003

黃超（1978-），男，江西樂安人，博士，研究方向為無線傳感器網絡、物聯網

2015-06-26

2015-08-05

針對事件驅動等應用中感知數據急劇增大的高負載網絡環境，提出基于無信標轉發的雙信道實時路由協議DBRR，該協議采用采用競爭模式與鄰居表相結合的轉發策略，競爭模式在線地選擇有效的轉發節點，并使用雙信道方式緩解高負載下的網絡沖突。DBRR通過速率約束和單跳延遲約束來滿足實時性，它鄰居表信息是通過競爭和無線廣播特性而不是信標廣播方式獲得。仿真結果表明，在高負載性網絡中，DBRR在數據傳輸成功率、傳輸延遲、平均能耗和通信代價等方面均明顯優于SPEED。

無線傳感器網絡；實時路由；雙信道；無信標轉發

廣東高校優秀青年創新人才培養計劃項目（No.2013LYM_0049）

Presents a dual-channel beaconless real-time routing protocol，called DBRR，for high-load wireless sensor networks（WSNs）.End-toend real-time requirements are fulfilled with speed or delay constraint at each hop through integrating the contention and neighbor table mechanisms.DBRR incorporates a dual-channel paradigm to alleviate packet collisions so as to lessen energy consumption and shorten end-to-end delay in high-load networks.Comprehensive simulations are carried out and show that DBRR outperform SPEED in terms of delivery ratio，end-to-end delay，energy efficiency and communication cost in high-load networks.