彭鑫+魏葉華+歐陽(yáng)竟成+劉樑驕

收稿日期：2013-05-28

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

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

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

文章編號(hào)：1003-6199（2014）03-0123-03

2.湖南大學(xué) 嵌入式與網(wǎng)絡(luò)計(jì)算湖南省重點(diǎn)實(shí)驗(yàn)室，湖南 長(zhǎng)沙 410082； 3.湖南師范大學(xué) 物理與信息科學(xué)學(xué)院，湖南 長(zhǎng)沙 410081）

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

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

中圖分類號(hào)：TP393 文獻(xiàn)標(biāo)識(shí)碼：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ú)線網(wǎng)絡(luò)（Wireless Multi-hop Networks）的機(jī)會(huì)路由（Opportunistic Routing）[1]過程將數(shù)據(jù)包轉(zhuǎn)發(fā)給多個(gè)下一跳候選節(jié)點(diǎn)。這種轉(zhuǎn)發(fā)模式使得數(shù)據(jù)產(chǎn)生多個(gè)副本，影響網(wǎng)絡(luò)性能。所以怎樣控制網(wǎng)絡(luò)中的冗余副本成為機(jī)會(huì)路由研究的熱點(diǎn)問題。

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

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

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

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

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

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

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

3 路由協(xié)議

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

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

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

2）s收到ACK（u），如果k=u則確認(rèn)節(jié)點(diǎn)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對(duì)提出的協(xié)議進(jìn)行了仿真，并與ExOR和基于地理位置的MGOR協(xié)議進(jìn)行了對(duì)比。

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

5 結(jié) 論

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

參考文獻(xiàn)

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

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

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

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

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

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

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

3 路由協(xié)議

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

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

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

2）s收到ACK（u），如果k=u則確認(rèn)節(jié)點(diǎn)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對(duì)提出的協(xié)議進(jìn)行了仿真，并與ExOR和基于地理位置的MGOR協(xié)議進(jìn)行了對(duì)比。

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

5 結(jié) 論

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

參考文獻(xiàn)

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

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

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

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

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

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

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

3 路由協(xié)議

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

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

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

2）s收到ACK（u），如果k=u則確認(rèn)節(jié)點(diǎn)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對(duì)提出的協(xié)議進(jìn)行了仿真，并與ExOR和基于地理位置的MGOR協(xié)議進(jìn)行了對(duì)比。

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

5 結(jié) 論

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

參考文獻(xiàn)

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