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

收稿日期：2013-05-28

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

作者簡介：彭 鑫（1981—），男，湖南岳陽人，講師，博士，研究方向：物聯(lián)網(wǎng)。

通訊聯(lián)系人，E-mail：yehua366@sohu.com

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

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

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

關(guān)鍵詞：多跳無線網(wǎng)絡(luò)；路由；轉(zhuǎn)發(fā)

中圖分類號：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 引 言

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

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

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

2 轉(zhuǎn)發(fā)開銷的確定

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

確定優(yōu)先級后轉(zhuǎn)發(fā)節(jié)點的選定以優(yōu)先級為基礎(chǔ)，選擇轉(zhuǎn)發(fā)開銷小的節(jié)點。本文通過期望轉(zhuǎn)發(fā)時間[7]來確定，令Ts表示當前轉(zhuǎn)發(fā)節(jié)點s的期望轉(zhuǎn)發(fā)時間，則：

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

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

3 路由協(xié)議

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

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

1）候選節(jié)點u收到數(shù)據(jù)包xi，并向s反饋ACK（u）；

2）s收到ACK（u），如果k=u則確認節(jié)點u收到xi，設(shè)置后續(xù)數(shù)據(jù)包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則轉(zhuǎn)發(fā)xi，否則，緩存。

4 仿真分析

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

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

5 結(jié) 論

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

參考文獻

[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.

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

2 轉(zhuǎn)發(fā)開銷的確定

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

確定優(yōu)先級后轉(zhuǎn)發(fā)節(jié)點的選定以優(yōu)先級為基礎(chǔ)，選擇轉(zhuǎn)發(fā)開銷小的節(jié)點。本文通過期望轉(zhuǎn)發(fā)時間[7]來確定，令Ts表示當前轉(zhuǎn)發(fā)節(jié)點s的期望轉(zhuǎn)發(fā)時間，則：

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

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

3 路由協(xié)議

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

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

1）候選節(jié)點u收到數(shù)據(jù)包xi，并向s反饋ACK（u）；

2）s收到ACK（u），如果k=u則確認節(jié)點u收到xi，設(shè)置后續(xù)數(shù)據(jù)包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則轉(zhuǎn)發(fā)xi，否則，緩存。

4 仿真分析

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

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

5 結(jié) 論

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

參考文獻

[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.

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

2 轉(zhuǎn)發(fā)開銷的確定

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

確定優(yōu)先級后轉(zhuǎn)發(fā)節(jié)點的選定以優(yōu)先級為基礎(chǔ)，選擇轉(zhuǎn)發(fā)開銷小的節(jié)點。本文通過期望轉(zhuǎn)發(fā)時間[7]來確定，令Ts表示當前轉(zhuǎn)發(fā)節(jié)點s的期望轉(zhuǎn)發(fā)時間，則：

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

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

3 路由協(xié)議

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

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

1）候選節(jié)點u收到數(shù)據(jù)包xi，并向s反饋ACK（u）；

2）s收到ACK（u），如果k=u則確認節(jié)點u收到xi，設(shè)置后續(xù)數(shù)據(jù)包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則轉(zhuǎn)發(fā)xi，否則，緩存。

4 仿真分析

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

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

5 結(jié) 論

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

參考文獻

[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.