WSN可靠路由機制分析

陳 昊

(中國勞動關系學院，北京 100044)

WSN可靠路由機制分析

陳 昊

(中國勞動關系學院，北京 100044)

傳統的多路徑傳輸路由來能夠提高傳輸的可靠性，但路徑的維護和更新需要消耗大量的資源。機會路由相對于傳統的路由策略，適用于無線傳感網傳輸，但面臨著同時傳播會有沖突的問題。本文結合可靠路由和機會路由，針對帶狀網絡區域，考慮以節點位置信息確定轉發候選節點優先級的機會路由能夠很好地平衡能耗和可靠傳輸的關系。

無線傳感網；機會路由；可靠傳輸

0 引言

數據收集是各種監測應用中的首要任務，感知節點需要將采集到的信息可靠地傳輸到sink節點，這對無線傳感網的傳輸可靠性、生命周期、通信代價等方面提出要求。由于路由策略對這些性能有至關重要的影響，所以，有效的路由機制是一個關鍵性問題。路由策略通常解決在一些其他性能標注約束下的最小化能量消耗[1]或傳輸延遲或傳輸代價[2-4]。然而，由于無線信道的不穩定會導致路由的不確定，影響數據傳輸的可靠性。因此，最近提出了一種新的適用于無線傳感網這類不可靠鏈路的多路徑的無線網絡路由機制，即機會路由（OR）[5]-[7]。機會路由相對于傳統的路由策略來說，下一跳不是確定的節點，而是一個可能的轉發節點候選集，發送節點基于鏈路質量作出概率性轉發決策以減少不確定的無線鏈路、泛洪延遲和冗余傳輸。然而，機會路由協議面臨著當有多個串音轉發者會有同時傳播的沖突和能量消耗的問題

1 研究現狀

1.1 可靠路由

可靠路由算法的主要功能是使得數據由源節點正確地傳輸到目的節點。它包括兩個方面的功能：第一是為不同的源節點和目的節點對選擇一條傳輸路徑；第二是在路由選好以后，將數據正確地由源節點傳送到目的節點。可靠路由問題就是找到滿足數據可靠傳輸的路徑的問題。

文獻[8-10]是通過提高傳輸速率來實現端到端的低傳輸時延，保證可靠的路由。SPEED[8]采用鄰居反饋策略(NFL)和反向壓力路由變更機制(BPR)避免鏈路擁塞和路由空洞，提高了傳輸可靠性和速率，但因沒有考慮節點的能量消耗情況，大大降低了網絡的整體壽命。文獻[11]提出將多報文和多路徑兩種方式相結合，即利用同一份數據沿同一條路徑發送多次和沿多條路徑同時發送相結合，主要是利用冗余數據的傳輸保障可靠性。該協議根據期望的可靠性和網絡的狀況決定轉發的份數和路徑數，達到較好的可靠性，但在負載增大加重了網絡負擔。ReInForm[12]也是依靠冗余數據的傳輸提高可靠性，該協議隨機選擇多條路徑，同時發送同一份數據。協議無需維護路徑，但每個節點需要掌握本節點和所有鄰居節點到sink的跳步數。MMSPEED[13]是一種同時滿足實時性和可靠性的多路徑傳輸協議。然而，此協議同上述協議一樣都缺乏對能量因素的考慮。

目前大多數路由算法采用多路徑傳輸方式來實現高可靠性傳輸，雖然該方式能夠提高傳輸的可靠性，但路徑的維護和更新需要消耗大量的資源，影響網絡的壽命，同時它們一般也很少考慮鏈路通信質量因素。

1.2 機會路由

2005年被首次提出了機會主義路由的概念，在很短的時間內，對其研究已經非常廣泛，同時大量的算法也相繼被提出。確定性路由協議中，為節點選擇單一中繼節點的理念在機會路由中不再使用，轉而通過多個潛在中繼節點競爭的方式，自主智能判斷進行下一跳轉發節點的選擇，用多個節點組成的轉發列表來替代確定性路由的單一中繼節點，達到了充分利用無線信道的廣播特性，提高了傳輸的可靠性。

按照網絡結構分類，機會主義路由包括有基礎設施支持和無基礎設施支持的路由。采用無基礎設施支持的機會主義路由技術不包含移動的或者固定的基礎設施，在網絡之中的通信實體通常是普通節點，且這些節點具有平等的地位，從而使得網絡具有更強的穩定性，較低的成本，有利于大規模部署。由于此類路由與無線傳感網的特性一致，使得我們對這一類路由更加關注。在無基礎設施支持的機會主義路由中，又包含了基于分發的和基于認知的機會主義路由。采用基于分發的路由技術，在將消息依次傳播到目的節點時需要通過全網絡的擴散，依靠節點間的接觸，消息能夠最終到達目的節點。在高移動性網絡或者中密集網絡中，基于分發路由技術的表現顯著地優于其他類型路由技術，并能夠確保最小的時延，代表的路由算法有OR-EAX、ORETX和GPSR[14]。

機會路由有以下兩部分組成：（i）轉發候選集選擇，確定轉發節點集合。（ii）轉播優先任務，決定轉發候選集合中的優先傳輸節點。在長城這類監測應用中，其特殊的帶狀網絡結構使得路由策略候選集的選擇有別于傳統區域。這是受帶狀區域垂直方向和拐彎處的寬度限制的。這里，定義從源節點到sink節點的直線方向為傳輸方向，即在選擇帶狀區域的轉發候選集時應該考慮傳輸方向。

然而現有的適用于帶狀網絡結構的解決方案只考慮了傳感器的部署，鮮有研究如何在線性拓撲網絡結構上部署節點以達到無線傳感網的最大的生命周期。給定已知數目的傳感器和特定的覆蓋要求，研究如何部署能夠達到最大化網絡生命期和最小化特定應用的代價這兩個目標。GUO 等人也研究了在監測石油管道的線性傳感器部署問題[15]。然后沒有其他的工作聚焦在像帶狀區域這樣的網絡結構下的路由策略上。

現有的工作考慮到的機會路由策略都是不考慮傳輸方向的。在機會路由領域，EXOR[7]，CBF[16]，MRD[17]和OMS[18]已經研究了多種開發無線廣播介質的技術和多種保證有效信息投遞的機會路由。EXOR是第一個研究路由和MAC技術來實現機會路由策略的實用系統。它廣播每一個包，選擇最好的接收者去轉發。然而，它在節點的轉發處理上定義了嚴格的調度。

有兩種典型的機會路由機制，基于地理位置輔助[5-6,19-20]和基于鏈路狀態[7,21]。一個最重要的機會路由機制是GeRaF[5]，地理位置上更靠近目的節點的轉發候選集擁有更高的轉播優先級。文獻[19]提出了移動adhoc網絡轉發的論點，討論了三個避免包復制的抑制策略。文獻[22]對比了諸如能耗，延遲，丟包率等性能。在無線傳感網這個領域，很少有工作聚焦在提供延遲保證和能量消耗的問題上。YU等人提出了多種技術來最小化通信延遲同時能夠維護能源效率[23]。最近，DSF[24]提出了一個新的數據轉發技術，能夠最優化數據傳輸率，端到端延遲或數據投遞的能源消耗。

然而，所有的這些GOR解決方案都盲目的把可獲得的下一跳鄰居節點作為轉發候選者，沒有解決方案研究了帶狀網絡結構下的傳輸方向。此外，機會路由機制還面臨著，當有多個數據同時傳輸時會產生沖突。根據上面的分析，顯而易見，帶狀網絡結構的路由與通常的應用環境有著顯著的不同。因此，應集中考慮以下兩個問題：

（1）已知帶狀網絡結構和傳播方向，怎么選擇轉發候選集。

（2）已知在傳播方向上的轉發候選集，怎么確定從每個傳感器到sink節點的路由策略。從而使在期望的網絡負載平衡下總的通信代價最最小，網絡生命周期最大。

在以上研究的基礎上，提出了在帶狀網絡中方向傳輸的基本思想。而且，把機會路由機制和傳輸方向結合在一起，從而達到了在預期網絡負載平衡的基礎上實現最小化網絡通信代價和最大化網絡生命周期的目標。

2 高可靠性保障的機會路由策略

在很多應用中，網絡的部署具有帶狀結構特點。比如管道監測[25-26]，水質監測[27]，道路監測，交通監測中，傳感器節點通常部署在管線，河流，道路的邊緣地帶。為便于研究，可以將部署環境抽象為具有代表性的兩種網絡結構，第一種為直線帶狀網絡，圖1所示，傳感器節點部署在近似于直線的狹窄的帶狀區域，sink節點放置在中心。另一種為轉彎帶狀網絡，圖2至圖4所示，與直線帶狀區域區別的是，存在一個夾角為θ的轉彎，0＜θ＜π。在此基礎上，以節點位置信息確定轉發候選節點優先級的基于地理位置的機會路由（GOR）是最佳選擇。

圖1 直線帶狀區域

圖2 帶拐角的帶狀區域-工形

圖3 帶拐角的帶狀區域-L形

圖4 帶拐角的帶狀區域-V形

假設無線傳感網被部署在形如石油管道這樣的帶狀區域的網絡結構環境中。無線傳感器網絡通常包含一個sink節點和一系列分散在sink節點周圍的源節點傳感器。在網絡結構處理時，任意傳感器節點的位置對定位算法而言都是已知的，sink節點的位置也是已知的。在這個方案中，傳感器節點感知環境信息，發送數據到被部署在帶狀區域中心的sink節點，專家可以根據傳感信息做出決策。

在現有的文獻下，全方位傳輸的隨機無線網絡經常被處理成歸一化單元密度的泊松點過程模型[28]。在固定的能量約束下，兩個節點只有在恒定的范圍r下可以互相通信。轉發候選者的成功選擇代表了網絡的連通性，上述隨機模型的連通性已經廣泛的被滲流理論模型所研究。因此一個自然而然的獲得最優候選集的方法就是用有方向的傳輸方法映射泊松點過程到一個滲流模型站點。

3 結 論

本文研究了可靠路由和機會路由的現有工作，分析特殊的監測區域帶狀網絡路由的特點，重點研究在帶狀網絡結構上的數據轉發的工作的缺乏，給出一個確定最優轉發候選集的思想。

[1] Mao X, Li X Y, Song W Z, et al. Energy efficient opportunistic routing in wireless networks[C]//Proceedings of the 12th ACM international conference on Modeling, analysis and simulation of wireless and mobile systems. ACM, 2009: 253-260.

[2] Zhong Z, Nelakuditi S. On the efficacy of opportunistic routing[C]//Sensor, Mesh and Ad Hoc Communications and Networks, 2007. SECON'07. 4th Annual IEEE Communications Society Conference on. IEEE, 2007: 441-450.

[3] Li Y, Chen W, Zhang Z L. Optimal forwarder list selection in opportunistic routing[C]//Mobile Adhoc and Sensor Systems, 2009. MASS'09. IEEE 6th International Conference on. IEEE, 2009: 670-675.

[4] Dubois-Ferrière H, Grossglauser M, Vetterli M. Valuable detours: Least-cost anypath routing[J]. Networking, IEEE/ACM Transactions on, 2011, 19(2): 333-346.

[5] Zorzi M, Rao R R. Geographic random forwarding (GeRaF) for adhoc and sensor networks: energy and latency performance[J]. Mobile Computing, IEEE Transactions on, 2003, 2(4): 349-365.

[6] Shah R C, Bonivento A, Petrovic D, et al. Joint optimization of a protocol stack for sensor networks[C]//Military Communications Conference, 2004. MILCOM 2004. 2004 IEEE.IEEE, 2004, 1: 480-486.

[7] Biswas S, Morris R. ExOR: opportunistic multi-hop routing for wireless networks[C]//ACM SIGCOMM Computer Communication Review. ACM, 2005, 35(4): 133-144.

[8] He T, Stankovic J A, Lu C, et al. SPEED: A stateless protocol for real-time communication in sensor networks[C]// Distributed Computing Systems, 2003. Proceedings. 23rd International Conference on. IEEE, 2003: 46-55.]

[9] Li Y, Chen C S, Song Y Q, et al. Enhancing real-time delivery in wireless sensor networks with two-hop information[J]. Industrial Informatics, IEEE Transactions on, 2009, 5(2): 113-122.

[10] Choi S C, Gong S L, Lee J W. An average velocity-based routing protocol with low end-to-end delay for wireless sensor networks[J]. Communications Letters, IEEE, 2009, 13(8): 621-623.

[11] Bhatnagar S, Deb B, Nath B. Service differentiation in sensor networks[C]//Proc. of Wireless Personal Multimedia Communications. 2001.

[12] Deb B, Bhatnagar S, Nath B. ReInForM: Reliable information forwarding using multiple paths in sensor networks[C]// Local Computer Networks, 2003. LCN'03. Proceedings. 28th Annual IEEE International Conference on. IEEE, 2003: 406-415. [13] Felemban E, Lee C G, Ekici E. MMSPEED: multipath Multi-SPEED protocol for QoS guarantee of reliability and. Timeliness in wireless sensor networks[J]. Mobile Computing, IEEE Transactions on, 2006, 5(6): 738-754.

[14] [GPSRKarp B, Kung H T. GPSR: Greedy perimeter stateless routing for wireless networks[C]//Proceedings of the 6th annual international conference on Mobile computing and networking. ACM, 2000: 243-254.

[15] Guo Y, Kong F, Zhu D, et al. Sensor placement for lifetime maximization in monitoring oil pipelines[C]//Proceedings of the 1st ACM/IEEE International Conference on Cyber-Physical Systems. ACM, 2010: 61-68.

[16] Cao Q, Abdelzaher T, He T, et al. Cluster-based forwarding for reliable end-to-end delivery in wireless sensor networks[C]// INFOCOM 2007. 26th IEEE International Conference on Computer Communications. IEEE. IEEE, 2007: 1928-1936.

[17] Miu A, Balakrishnan H, Koksal C E. Improving loss resilience with multi-radio diversity in wireless networks[C]//Proceedings of the 11th annual international conference on Mobile computing and networking. ACM, 2005: 16-30.

[18] Cetinkaya C, Knightly E W. Opportunistic traffic scheduling over multiple network paths[C]//INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies. IEEE, 2004, 3: 1928-1937.

[19] Fü?ler H, Widmer J, K?semann M, et al. Contention-based forwarding for mobile ad hoc networks[J]. Ad Hoc Networks, 2003, 1(4): 351-369.

[20] Zeng K, Yang Z, Lou W. Location-aided opportunistic forwarding in multirate and multihop wireless networks[J]. Vehicular Technology, IEEE Transactions on, 2009, 58(6): 3032-3040.

[21] Dubois-Ferriere H, Grossglauser M, Vetterli M. Least-cost opportunistic routing[C]//Proceedings of 2007 Allerton Conference on Communication, Control, and Computing. 2007, 11: 13-39.

[22] Shah R C, Wietholter S, Wolisz A, et al. When does opportunistic routing make sense?[C]//Pervasive Computing and Communications Workshops, 2005. PerCom 2005 Workshops. Third IEEE International Conference on. IEEE, 2005: 350-356.

[23] Yu Y, Krishnamachari B, Prasanna V K. Energy-latency tradeoffs for data gathering in wireless sensor networks[C]// INFOCOM 2004. Twenty-third AnnualJoint Conference of the IEEE Computer and Communications Societies. IEEE, 2004, 1.

[24] Gu Y, He T. Data forwarding in extremely low duty-cycle sensor networks with unreliable communication links[C]// Proceedings of the 5th international conference on Embedded networked sensor systems. ACM, 2007: 321-334.

[25] Stoianov I, Nachman L, Madden S, et al. PIPENET: A wireless sensor network for pipeline monitoring[C]// Information Processing in Sensor Networks, 2007. IPSN 2007. 6th International Symposium on. IEEE, 2007: 264-273.

[26] Guo Y, Kong F, Zhu D, et al. Sensor placement for lifetime maximization in monitoring oil pipelines[C]//Proceedings of the 1st ACM/IEEE International Conference on Cyber-Physical Systems. ACM, 2010: 61-68.

[27] O'Flyrm B, Martinez R, Cleary J, et al. SmartCoast: a wireless sensor network for water quality monitoring[C]//Local Computer Networks, 2007. LCN 2007. 32nd IEEE Conference on. Ieee, 2007: 815-816.

[28] Chau C K, Gibbens R J, Towsley D. Impact of directional transmission in large-scale multi-hop wireless ad hoc networks[C]//INFOCOM, 2012 Proceedings IEEE. IEEE, 2012: 522-530.

WSN Reliable Routing Protocol Analysis

CHEN Hao
(China Institute of Industrial Relations, Beijing)

The traditional multipath transmission path can improve the transmission reliability, but new path maintenance needs to consume large amounts of resources. Opportunistic routing protocol is more suitable for wireless sensor network transmission, but faces the problem of simultaneous transmission conflict. This paper combines reliable routing and opportunistic routing to consider opportunistic routing with forwarding node priority by node location information. This idea can balance the relationship between energy consumption and reliable transmission.

WSN, Opportunistic routing, Reliable transmission

TP212.9

ADOI：10.3969/j.issn.1003-6970.2016.12.044

中國勞動關系學院院級項目12zy020和一般項目“無線傳感網擁塞控制技術的研究與應用”資助。

陳昊，女，副教授，博士，主研方向：無線傳感器網絡。

本文著錄格式：陳昊. WSN可靠路由機制分析[J]. 軟件，2016，37（12）：206-209