具有副本抑制能力的多跳無線網絡路由協議

彭鑫+魏葉華+歐陽竟成+劉樑驕

收稿日期：2013-05-28

基金項目：國家自然科學基金項目（61173036， 61300039， 61272061）；湖南省教育廳重點項目（12A057）；湖南省高校科技創新團隊支持計劃（湘教通[2012]318）；中國博士后基金面上項目（2013M542109）；湖南省自然科學基金項目（14JJ3130）

作者簡介：彭 鑫（1981—），男，湖南岳陽人，講師，博士，研究方向：物聯網。

通訊聯系人，E-mail：yehua366@sohu.com

文章編號：1003-6199（2014）03-0123-03

2.湖南大學 嵌入式與網絡計算湖南省重點實驗室，湖南 長沙 410082； 3.湖南師范大學 物理與信息科學學院，湖南 長沙 410081）

摘 要：針對多跳無線網絡中機會路由的副本傳輸問題，提出一種新的機會路由協議。提出的策略不再簡單采用單跳廣播的方式轉發數據，而是通過節點間的距離確定轉發開銷，再讓數據包攜帶下一跳候選節點信息并根據候選節點的ACK選擇下一跳節點，從而保證了每個數據包只有一個候選節點進行轉發。仿真結果顯示，提出的方案能減少不必要的傳輸行為，有效改善了網絡吞吐率。

關鍵詞：多跳無線網絡；路由；轉發

中圖分類號：TP393 文獻標識碼：A

Routing Protocol with Duplicate Inhibit in Multi-hop Wireless Networks

PENG Xin1，2， WEI Ye-hua3， OUYANG Jing-cheng1， LIU Liang-jiao2

（1.Key Laboratory on Complex Systems Optimization and Controlling of Hunan High Education Institutions， College

of Information and Communication Engineering， Hunan Institute of Science and Technology， Yueyang，Hunan 414000，China；

2.Key Laboratory for Embedded and Network Computing of Hunan Province， Hunan University， Changsha，Hunan 410082，China；

3.Institute of Physics and Information Science， Hunan Normal University， Changsha，Hunan 410081，China）

Abstract：A novel protocol of duplicate elimination in opportunistic routing was introduced. At first we decide the priority of candidate nodes by computing the distance of candidate node among present node and destination node. The protocol allows each node to control relay transmissions of its next hop candidate nodes using information piggybacked on packets. The protocol guarantees that for each packet， only one candidate node that correctly receives the packet can deliver the packet. Simulation results show that the protocol achieves higher throughput than existing opportunistic routing protocols by reducing duplicate packets.

Key words：multi-hop wireless networks； routing；forward

1 引 言

多跳無線網絡（Wireless Multi-hop Networks）的機會路由（Opportunistic Routing）[1]過程將數據包轉發給多個下一跳候選節點。這種轉發模式使得數據產生多個副本，影響網絡性能。所以怎樣控制網絡中的冗余副本成為機會路由研究的熱點問題。

ExOR[2]路由協議使每個節點周期性發送探測包，獲得相鄰鏈路的ETX（Expected Transmission Count）并進行廣播，從而讓每個節點獲得全部鏈路的狀態。當某節點需要發送數據，采用Dijkstra算法計算自己的鄰居到目的ETX，然后選擇到目的節點的最短ETX小于自身的節點作為備選節點，并根據其到目的節點的距離設置轉發優先級。但是ExOR需要每個節點廣播鏈路消息，網絡負載較大，并且缺乏副本控制機制。MORE[3]協議引入流內隨機網絡編碼來降低副本產生的概率。協議對發送的數據進行分批，然后作隨機線性編碼并廣播。中間節點收到數據包后判斷是否與本地數據包線性獨立，若線性獨立則緩存在本地，否則丟棄。CORE[4]協議針對基于局部信息網絡編碼方案只能被動利用各節點現有的編碼機會，將局部流間網絡編碼應用于機會路由。在確定候選轉發節點優先級時，編碼機會越大的節點優先級越高，從而確保編碼機會多的節點轉發數據包。SOAR[5]協議首先建立到目的節點的最短路徑，協議以偏離這條路徑的跳數作為候選節點的選擇參數，并且各候選節點間鏈路的ETX必須高于一定門限使得候選節點集分布在最短路徑附近，減少了副本的產生。MGOR[6]協議的每個節點可以有不同的速率和不同的轉發范圍，從而導致候選轉發節點集和優先級關系的變化。MGOR采用EOT（Expected One-hop Throughput）作為候選節點選擇尺度來實現候選節點的選擇和傳輸速率的平衡優化。

本文提出一種滿足副本控制要求的機會路由協議。該協議無需候選節點進行任何信息交換，只需當前節點轉發數據包時，附帶少量控制信息即可指定下一跳候選節點，實現副本控制要求。

2 轉發開銷的確定

假設每個轉發節點知道下一跳候選節點。協議首先確定候選節點的轉發開銷。如果多個候選節點收到數據包，那么開銷低的節點進行轉發，這樣可有效降低總體傳輸開銷。確定候選節點轉發開銷首先要確定其優先級，而優先級與鏈路的可靠性和路由有效性有關。由于鏈路可靠性與節點間的距離密切相關，本文通過節點距離判定候選節點的優先級。通常節點都能夠獲取相鄰節點間的距離，對于相距較遠的節點，只能通過計算得到。本文通過網絡拓撲圖的確定性求解節點間的距離數據。對于有n個節點的網絡，令dij表示節點i和j的距離。建立矩陣P=[pij]n*n，其中如果i和j的距離可以直接測量，那么pij=dij2；如果i和j的距離不能直接測量那么取pij=0，表示距離未知。然后對P進行奇異值分解，并取P的前3個奇異值向量構造P3作為2維空間距離矩陣。如果用C表示節點s的候選節點集，那么應滿足條件v∈C，有dvd≤dsd，即候選節點v離節點d的距離要近。節點的優先級排序準則為，候選節點到當前轉發節點s和目的節點d的距離之和越小優先級越高。

確定優先級后轉發節點的選定以優先級為基礎，選擇轉發開銷小的節點。本文通過期望轉發時間[7]來確定，令Ts表示當前轉發節點s的期望轉發時間，則：

Ts=1p（t+∑Cj=1qs（j-1）·ps，C（j）·TC（j）（1）

其中，p表示數據包成功發送的概率，C（j）表示候選節點集中第j優先級的節點，T表示該節點的期望傳輸時間。Ps，C（j）表示節點C（j）從節點s成功接收數據包的概率，qs（j）表示優先級最高的j個候選節點均未能成功接收數據包的概率。t表示數據包的發送時間。

3 路由協議

當前轉發節點s發送數據包后，通過候選節點的ACK確定哪些節點收到了數據包，然后根據轉發開銷確定下一跳節點。s將相關信息附帶在后續數據包上，候選節點則通過數據包攜帶的信息，確定自己是否應當轉發之前收到的數據包。每跳轉發依此進行，直到將數據包送達目的節點。假設源節點發送數據包x1，x2，…，xi到目的節點，其中i表示數據包的序號。中間節點為每個候選節點建立局部變量保存數據包的序號以及候選節點的ID。a（u）表示節點s建立的候選節點u的局部變量，變量值為數據包序號，用于告知候選節點u是否轉發之前收到第a（u）個數據包。s轉發的每個數據包都會插入α（u）。候選節點收到數據包后緩存在本地。對于候選節點u收到數據包，如果發現數據包的a（u）=i，那么u將轉發之前緩存的數據包xi。候選節點每接收到一個數據包要向上一跳節點s發送ACK確認。如果沒有收到ACK，節點s將會重傳。

對于節點s，令Ci表示收到數據包xi的候選節點集，|Ci|=f，Ni表示節點s的鄰居節點集，|Ni|=g。Ci（1）表示集合Ci中優先級最高的節點。選擇候選節點的關鍵是節點s如何通過數據包xi完成下一跳節點的選擇，也就是讓a（Ci1）=i，路由過程如下：

1）候選節點u收到數據包xi，并向s反饋ACK（u）；

2）s收到ACK（u），如果k=u則確認節點u收到xi，設置后續數據包xi+n的α（u）；

3）如果uCi，那么xi+n，α（u）不變；

4）如果u=Ci（1），那么α（Ci（1））=i；

5）如果u∈{v|v∈Ci&v≠Ci（1）}，則α（u）為空；

6）如果α（u）=i則轉發xi，否則，緩存。

4 仿真分析

本文通過NS2對提出的協議進行了仿真，并與ExOR和基于地理位置的MGOR協議進行了對比。

在NS2中模擬1000×1000m的仿真區域，布設100個節點。首先，分析三種協議在不同路徑長度下的性能，如圖1。圖中給出了端到端平均傳輸次數與最短路由路徑長度的比值。不難看出本文協議具有較低的傳輸次數，從而具有較高的吞吐率。圖2給出了在不同數據流的條件下，幾種協議的吞吐率性能，實驗中隨機選取源節點和目的節點。不難看出ExOR與MGOR和本文協議有較大差距，而且隨數據流的增多，由于虛警率的上升MGOR與本文協議在性能上的差距開始顯現。在數據流較少的情況下，本協議的吞吐率相對于ExOR提升70%，相對于MGOR改進11.3%。

5 結 論

本文提出了具有副本控制能力的機會路由協議。提出的協議通過候選節點的距離確定其優先級，然后盡量選擇轉發時間開銷較小的候選節點。協議通過包賦值控制下一跳候選節點的轉發，而非通過單跳廣播形式進行傳輸，保證了每個數據包只有一個節點能轉發。仿真結果顯示協議通過降低不必要的副本開銷，顯著改善了吞吐率。

參考文獻

[1] ZHANG Z. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks： Overview and challenges[J]. IEEE Communications Surveys & Tutorials， 2006，8（1）：24-37.

[2] BISWAS S，MORRIS R. ExOR： opportunistic multi-hop routing for wireless networks[J]. In Proc. of 2005 Conference on Applications， Technologies ， Architectures， and protocols for computer communications （SIGCOMM05） ACM， 2005， 133-144.

[3] CHACHULSKI S，JENNINGS M，KATTI S，KATABI D.Trading structure for randomness in wireless opportunistic routing[J]. In Proc. of 2007 ACM SIGCOMM， 169–180.

[4] YAN Y，ZHANG BX，ZHENG J，MA J. CORE： A coding-aware opportunistic routing mechanism for wireless mesh networks[J]. IEEE Wireless Communications， 2010，17（3）：96-103.

[5] ROZNER E，SESHADRI J，MEHTA Y，QIU L. Simple opportunistic routing protocol for wireless mesh networks[J]. In Proc. of the IEEE WiMesh 2006. Washington： IEEE Computer Society Press， 2006. 48-54.

[6] ZENG K，LOU W，ZHAI H.On end-to-end throughput of opportunistic routing in multirate and multihop wireless networks[J]. In： Proc. of the IEEE INFOCOM 2008. Washington： IEEE Computer Society Press， 2008. 816-824.

[7] LAUFER R，DUBOIS-FERRIERE H，KLEINROCK L. Multirate anypath routing in wireless mesh networks[J]. In Proc. of 2009 IEEE INFOCOM， 2009： 37-45.

本文提出一種滿足副本控制要求的機會路由協議。該協議無需候選節點進行任何信息交換，只需當前節點轉發數據包時，附帶少量控制信息即可指定下一跳候選節點，實現副本控制要求。

2 轉發開銷的確定

假設每個轉發節點知道下一跳候選節點。協議首先確定候選節點的轉發開銷。如果多個候選節點收到數據包，那么開銷低的節點進行轉發，這樣可有效降低總體傳輸開銷。確定候選節點轉發開銷首先要確定其優先級，而優先級與鏈路的可靠性和路由有效性有關。由于鏈路可靠性與節點間的距離密切相關，本文通過節點距離判定候選節點的優先級。通常節點都能夠獲取相鄰節點間的距離，對于相距較遠的節點，只能通過計算得到。本文通過網絡拓撲圖的確定性求解節點間的距離數據。對于有n個節點的網絡，令dij表示節點i和j的距離。建立矩陣P=[pij]n*n，其中如果i和j的距離可以直接測量，那么pij=dij2；如果i和j的距離不能直接測量那么取pij=0，表示距離未知。然后對P進行奇異值分解，并取P的前3個奇異值向量構造P3作為2維空間距離矩陣。如果用C表示節點s的候選節點集，那么應滿足條件v∈C，有dvd≤dsd，即候選節點v離節點d的距離要近。節點的優先級排序準則為，候選節點到當前轉發節點s和目的節點d的距離之和越小優先級越高。

確定優先級后轉發節點的選定以優先級為基礎，選擇轉發開銷小的節點。本文通過期望轉發時間[7]來確定，令Ts表示當前轉發節點s的期望轉發時間，則：

Ts=1p（t+∑Cj=1qs（j-1）·ps，C（j）·TC（j）（1）

其中，p表示數據包成功發送的概率，C（j）表示候選節點集中第j優先級的節點，T表示該節點的期望傳輸時間。Ps，C（j）表示節點C（j）從節點s成功接收數據包的概率，qs（j）表示優先級最高的j個候選節點均未能成功接收數據包的概率。t表示數據包的發送時間。

3 路由協議

當前轉發節點s發送數據包后，通過候選節點的ACK確定哪些節點收到了數據包，然后根據轉發開銷確定下一跳節點。s將相關信息附帶在后續數據包上，候選節點則通過數據包攜帶的信息，確定自己是否應當轉發之前收到的數據包。每跳轉發依此進行，直到將數據包送達目的節點。假設源節點發送數據包x1，x2，…，xi到目的節點，其中i表示數據包的序號。中間節點為每個候選節點建立局部變量保存數據包的序號以及候選節點的ID。a（u）表示節點s建立的候選節點u的局部變量，變量值為數據包序號，用于告知候選節點u是否轉發之前收到第a（u）個數據包。s轉發的每個數據包都會插入α（u）。候選節點收到數據包后緩存在本地。對于候選節點u收到數據包，如果發現數據包的a（u）=i，那么u將轉發之前緩存的數據包xi。候選節點每接收到一個數據包要向上一跳節點s發送ACK確認。如果沒有收到ACK，節點s將會重傳。

對于節點s，令Ci表示收到數據包xi的候選節點集，|Ci|=f，Ni表示節點s的鄰居節點集，|Ni|=g。Ci（1）表示集合Ci中優先級最高的節點。選擇候選節點的關鍵是節點s如何通過數據包xi完成下一跳節點的選擇，也就是讓a（Ci1）=i，路由過程如下：

1）候選節點u收到數據包xi，并向s反饋ACK（u）；

2）s收到ACK（u），如果k=u則確認節點u收到xi，設置后續數據包xi+n的α（u）；

3）如果uCi，那么xi+n，α（u）不變；

4）如果u=Ci（1），那么α（Ci（1））=i；

5）如果u∈{v|v∈Ci&v≠Ci（1）}，則α（u）為空；

6）如果α（u）=i則轉發xi，否則，緩存。

4 仿真分析

本文通過NS2對提出的協議進行了仿真，并與ExOR和基于地理位置的MGOR協議進行了對比。

在NS2中模擬1000×1000m的仿真區域，布設100個節點。首先，分析三種協議在不同路徑長度下的性能，如圖1。圖中給出了端到端平均傳輸次數與最短路由路徑長度的比值。不難看出本文協議具有較低的傳輸次數，從而具有較高的吞吐率。圖2給出了在不同數據流的條件下，幾種協議的吞吐率性能，實驗中隨機選取源節點和目的節點。不難看出ExOR與MGOR和本文協議有較大差距，而且隨數據流的增多，由于虛警率的上升MGOR與本文協議在性能上的差距開始顯現。在數據流較少的情況下，本協議的吞吐率相對于ExOR提升70%，相對于MGOR改進11.3%。

5 結 論

本文提出了具有副本控制能力的機會路由協議。提出的協議通過候選節點的距離確定其優先級，然后盡量選擇轉發時間開銷較小的候選節點。協議通過包賦值控制下一跳候選節點的轉發，而非通過單跳廣播形式進行傳輸，保證了每個數據包只有一個節點能轉發。仿真結果顯示協議通過降低不必要的副本開銷，顯著改善了吞吐率。

參考文獻

[1] ZHANG Z. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks： Overview and challenges[J]. IEEE Communications Surveys & Tutorials， 2006，8（1）：24-37.

[2] BISWAS S，MORRIS R. ExOR： opportunistic multi-hop routing for wireless networks[J]. In Proc. of 2005 Conference on Applications， Technologies ， Architectures， and protocols for computer communications （SIGCOMM05） ACM， 2005， 133-144.

[3] CHACHULSKI S，JENNINGS M，KATTI S，KATABI D.Trading structure for randomness in wireless opportunistic routing[J]. In Proc. of 2007 ACM SIGCOMM， 169–180.

[4] YAN Y，ZHANG BX，ZHENG J，MA J. CORE： A coding-aware opportunistic routing mechanism for wireless mesh networks[J]. IEEE Wireless Communications， 2010，17（3）：96-103.

[5] ROZNER E，SESHADRI J，MEHTA Y，QIU L. Simple opportunistic routing protocol for wireless mesh networks[J]. In Proc. of the IEEE WiMesh 2006. Washington： IEEE Computer Society Press， 2006. 48-54.

[6] ZENG K，LOU W，ZHAI H.On end-to-end throughput of opportunistic routing in multirate and multihop wireless networks[J]. In： Proc. of the IEEE INFOCOM 2008. Washington： IEEE Computer Society Press， 2008. 816-824.

[7] LAUFER R，DUBOIS-FERRIERE H，KLEINROCK L. Multirate anypath routing in wireless mesh networks[J]. In Proc. of 2009 IEEE INFOCOM， 2009： 37-45.

本文提出一種滿足副本控制要求的機會路由協議。該協議無需候選節點進行任何信息交換，只需當前節點轉發數據包時，附帶少量控制信息即可指定下一跳候選節點，實現副本控制要求。

2 轉發開銷的確定

假設每個轉發節點知道下一跳候選節點。協議首先確定候選節點的轉發開銷。如果多個候選節點收到數據包，那么開銷低的節點進行轉發，這樣可有效降低總體傳輸開銷。確定候選節點轉發開銷首先要確定其優先級，而優先級與鏈路的可靠性和路由有效性有關。由于鏈路可靠性與節點間的距離密切相關，本文通過節點距離判定候選節點的優先級。通常節點都能夠獲取相鄰節點間的距離，對于相距較遠的節點，只能通過計算得到。本文通過網絡拓撲圖的確定性求解節點間的距離數據。對于有n個節點的網絡，令dij表示節點i和j的距離。建立矩陣P=[pij]n*n，其中如果i和j的距離可以直接測量，那么pij=dij2；如果i和j的距離不能直接測量那么取pij=0，表示距離未知。然后對P進行奇異值分解，并取P的前3個奇異值向量構造P3作為2維空間距離矩陣。如果用C表示節點s的候選節點集，那么應滿足條件v∈C，有dvd≤dsd，即候選節點v離節點d的距離要近。節點的優先級排序準則為，候選節點到當前轉發節點s和目的節點d的距離之和越小優先級越高。

確定優先級后轉發節點的選定以優先級為基礎，選擇轉發開銷小的節點。本文通過期望轉發時間[7]來確定，令Ts表示當前轉發節點s的期望轉發時間，則：

Ts=1p（t+∑Cj=1qs（j-1）·ps，C（j）·TC（j）（1）

其中，p表示數據包成功發送的概率，C（j）表示候選節點集中第j優先級的節點，T表示該節點的期望傳輸時間。Ps，C（j）表示節點C（j）從節點s成功接收數據包的概率，qs（j）表示優先級最高的j個候選節點均未能成功接收數據包的概率。t表示數據包的發送時間。

3 路由協議

當前轉發節點s發送數據包后，通過候選節點的ACK確定哪些節點收到了數據包，然后根據轉發開銷確定下一跳節點。s將相關信息附帶在后續數據包上，候選節點則通過數據包攜帶的信息，確定自己是否應當轉發之前收到的數據包。每跳轉發依此進行，直到將數據包送達目的節點。假設源節點發送數據包x1，x2，…，xi到目的節點，其中i表示數據包的序號。中間節點為每個候選節點建立局部變量保存數據包的序號以及候選節點的ID。a（u）表示節點s建立的候選節點u的局部變量，變量值為數據包序號，用于告知候選節點u是否轉發之前收到第a（u）個數據包。s轉發的每個數據包都會插入α（u）。候選節點收到數據包后緩存在本地。對于候選節點u收到數據包，如果發現數據包的a（u）=i，那么u將轉發之前緩存的數據包xi。候選節點每接收到一個數據包要向上一跳節點s發送ACK確認。如果沒有收到ACK，節點s將會重傳。

對于節點s，令Ci表示收到數據包xi的候選節點集，|Ci|=f，Ni表示節點s的鄰居節點集，|Ni|=g。Ci（1）表示集合Ci中優先級最高的節點。選擇候選節點的關鍵是節點s如何通過數據包xi完成下一跳節點的選擇，也就是讓a（Ci1）=i，路由過程如下：

1）候選節點u收到數據包xi，并向s反饋ACK（u）；

2）s收到ACK（u），如果k=u則確認節點u收到xi，設置后續數據包xi+n的α（u）；

3）如果uCi，那么xi+n，α（u）不變；

4）如果u=Ci（1），那么α（Ci（1））=i；

5）如果u∈{v|v∈Ci&v≠Ci（1）}，則α（u）為空；

6）如果α（u）=i則轉發xi，否則，緩存。

4 仿真分析

本文通過NS2對提出的協議進行了仿真，并與ExOR和基于地理位置的MGOR協議進行了對比。

在NS2中模擬1000×1000m的仿真區域，布設100個節點。首先，分析三種協議在不同路徑長度下的性能，如圖1。圖中給出了端到端平均傳輸次數與最短路由路徑長度的比值。不難看出本文協議具有較低的傳輸次數，從而具有較高的吞吐率。圖2給出了在不同數據流的條件下，幾種協議的吞吐率性能，實驗中隨機選取源節點和目的節點。不難看出ExOR與MGOR和本文協議有較大差距，而且隨數據流的增多，由于虛警率的上升MGOR與本文協議在性能上的差距開始顯現。在數據流較少的情況下，本協議的吞吐率相對于ExOR提升70%，相對于MGOR改進11.3%。

5 結 論

本文提出了具有副本控制能力的機會路由協議。提出的協議通過候選節點的距離確定其優先級，然后盡量選擇轉發時間開銷較小的候選節點。協議通過包賦值控制下一跳候選節點的轉發，而非通過單跳廣播形式進行傳輸，保證了每個數據包只有一個節點能轉發。仿真結果顯示協議通過降低不必要的副本開銷，顯著改善了吞吐率。

參考文獻

[1] ZHANG Z. Routing in intermittently connected mobile ad hoc networks and delay tolerant networks： Overview and challenges[J]. IEEE Communications Surveys & Tutorials， 2006，8（1）：24-37.

[2] BISWAS S，MORRIS R. ExOR： opportunistic multi-hop routing for wireless networks[J]. In Proc. of 2005 Conference on Applications， Technologies ， Architectures， and protocols for computer communications （SIGCOMM05） ACM， 2005， 133-144.

[3] CHACHULSKI S，JENNINGS M，KATTI S，KATABI D.Trading structure for randomness in wireless opportunistic routing[J]. In Proc. of 2007 ACM SIGCOMM， 169–180.

[4] YAN Y，ZHANG BX，ZHENG J，MA J. CORE： A coding-aware opportunistic routing mechanism for wireless mesh networks[J]. IEEE Wireless Communications， 2010，17（3）：96-103.

[5] ROZNER E，SESHADRI J，MEHTA Y，QIU L. Simple opportunistic routing protocol for wireless mesh networks[J]. In Proc. of the IEEE WiMesh 2006. Washington： IEEE Computer Society Press， 2006. 48-54.

[6] ZENG K，LOU W，ZHAI H.On end-to-end throughput of opportunistic routing in multirate and multihop wireless networks[J]. In： Proc. of the IEEE INFOCOM 2008. Washington： IEEE Computer Society Press， 2008. 816-824.

[7] LAUFER R，DUBOIS-FERRIERE H，KLEINROCK L. Multirate anypath routing in wireless mesh networks[J]. In Proc. of 2009 IEEE INFOCOM， 2009： 37-45.