陳 昊

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

WSN可靠路由機制分析

陳 昊

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

傳統(tǒng)的多路徑傳輸路由來能夠提高傳輸?shù)目煽啃?，但路徑的維護和更新需要消耗大量的資源。機會路由相對于傳統(tǒng)的路由策略，適用于無線傳感網(wǎng)傳輸，但面臨著同時傳播會有沖突的問題。本文結(jié)合可靠路由和機會路由，針對帶狀網(wǎng)絡區(qū)域，考慮以節(jié)點位置信息確定轉(zhuǎn)發(fā)候選節(jié)點優(yōu)先級的機會路由能夠很好地平衡能耗和可靠傳輸?shù)年P系。

無線傳感網(wǎng)；機會路由；可靠傳輸

0 引言

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

1 研究現(xiàn)狀

1.1 可靠路由

可靠路由算法的主要功能是使得數(shù)據(jù)由源節(jié)點正確地傳輸?shù)侥康墓?jié)點。它包括兩個方面的功能：第一是為不同的源節(jié)點和目的節(jié)點對選擇一條傳輸路徑；第二是在路由選好以后，將數(shù)據(jù)正確地由源節(jié)點傳送到目的節(jié)點?？煽柯酚蓡栴}就是找到滿足數(shù)據(jù)可靠傳輸?shù)穆窂降膯栴}。

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

目前大多數(shù)路由算法采用多路徑傳輸方式來實現(xiàn)高可靠性傳輸，雖然該方式能夠提高傳輸?shù)目煽啃裕窂降木S護和更新需要消耗大量的資源，影響網(wǎng)絡的壽命，同時它們一般也很少考慮鏈路通信質(zhì)量因素。

1.2 機會路由

2005年被首次提出了機會主義路由的概念，在很短的時間內(nèi)，對其研究已經(jīng)非常廣泛，同時大量的算法也相繼被提出。確定性路由協(xié)議中，為節(jié)點選擇單一中繼節(jié)點的理念在機會路由中不再使用，轉(zhuǎn)而通過多個潛在中繼節(jié)點競爭的方式，自主智能判斷進行下一跳轉(zhuǎn)發(fā)節(jié)點的選擇，用多個節(jié)點組成的轉(zhuǎn)發(fā)列表來替代確定性路由的單一中繼節(jié)點，達到了充分利用無線信道的廣播特性，提高了傳輸?shù)目煽啃浴?/p>

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

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

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

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

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

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

（1）已知帶狀網(wǎng)絡結(jié)構(gòu)和傳播方向，怎么選擇轉(zhuǎn)發(fā)候選集。

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

在以上研究的基礎上，提出了在帶狀網(wǎng)絡中方向傳輸?shù)幕舅枷?。而且，把機會路由機制和傳輸方向結(jié)合在一起，從而達到了在預期網(wǎng)絡負載平衡的基礎上實現(xiàn)最小化網(wǎng)絡通信代價和最大化網(wǎng)絡生命周期的目標。

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

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

圖1 直線帶狀區(qū)域

圖2 帶拐角的帶狀區(qū)域-工形

圖3 帶拐角的帶狀區(qū)域-L形

圖4 帶拐角的帶狀區(qū)域-V形

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

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

3 結(jié) 論

本文研究了可靠路由和機會路由的現(xiàn)有工作，分析特殊的監(jiān)測區(qū)域帶狀網(wǎng)絡路由的特點，重點研究在帶狀網(wǎng)絡結(jié)構(gòu)上的數(shù)據(jù)轉(zhuǎn)發(fā)的工作的缺乏，給出一個確定最優(yōu)轉(zhuǎn)發(fā)候選集的思想。

[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和一般項目“無線傳感網(wǎng)擁塞控制技術的研究與應用”資助。

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

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