聶 志，劉 靜，甘小鶯，徐友云，劉漢春

(1.上海交通大學電子工程系無線通信技術研究所，上海 200240;2.綜合業(yè)務網(wǎng)理論及關鍵技術國家重點實驗室，陜西 西安 710071;3.上海數(shù)字多媒體處理與傳輸重點實驗室，上海 200240)

0 引言

近年來，研究者提出了許多應用于移動無線自組織(Ad Hoc)網(wǎng)絡的路由協(xié)議［1-5］。這些路由協(xié)議大致可分為2種類型:傳統(tǒng)移動Ad Hoc路由協(xié)議和移動Ad Hoc機會路由協(xié)議［6］。傳統(tǒng)Ad Hoc路由協(xié)議大多數(shù)是從有線網(wǎng)絡發(fā)展而來，這些協(xié)議常常選擇一條從源節(jié)點到目的節(jié)點的固定路徑，在整個業(yè)務傳輸?shù)倪^程中，均使用這條路徑進行傳輸直至傳輸完畢或者此路徑失效，如經(jīng)典的 DSR［1］和 AODV［2］路由協(xié)議。然而，這樣的靜態(tài)路由策略需要建立端到端的基于全局鏈路狀態(tài)的路由，需要存儲路由信息表，需要在數(shù)據(jù)傳輸過程中維持一條固定的路由。顯然這樣的路由協(xié)議并不適用于具有移動節(jié)點的Ad Hoc網(wǎng)絡。因此在傳統(tǒng)路由中，節(jié)點的移動性成了影響網(wǎng)絡各項性能的一個很重要的原因。

基于上述原因，研究者們提出了一種新的應用于移動Ad Hoc網(wǎng)絡的路由技術—機會路由。機會路由是和傳統(tǒng)路由截然不同的一種應用于無線多跳網(wǎng)絡的路由技術，其特征在于，它不是在傳輸開始之前預先指定一條固定的傳輸路徑，而是在每一跳結(jié)束以后，動態(tài)地選擇一個合適的節(jié)點作為轉(zhuǎn)發(fā)節(jié)點繼續(xù)傳輸［7-9］。機會路由可以解決傳統(tǒng)路由中因節(jié)點移動性而導致的某條路徑頻繁失效的問題，同時能很好地利用無線傳輸廣播的特性和空間分集，降低鏈路質(zhì)量波動所帶來的影響［5，10］。機會路由所帶來的眾多好處使其成為了當前移動Ad Hoc網(wǎng)絡路由技術中的一項熱點研究對象，本文所做的工作也是應用于機會路由的。

目前，大多數(shù)機會路由協(xié)議中所使用的轉(zhuǎn)發(fā)策略為貪婪轉(zhuǎn)發(fā)策略［7-8，11-12］。貪婪轉(zhuǎn)發(fā)策略指轉(zhuǎn)發(fā)節(jié)點在鄰居節(jié)點中找一個離目的節(jié)點最近且比轉(zhuǎn)發(fā)節(jié)點離目的節(jié)點距離更近的節(jié)點作為下一跳節(jié)點。機會路由協(xié)議GeRaF就是采用了貪婪轉(zhuǎn)發(fā)策略的一個很經(jīng)典的路由協(xié)議，它根據(jù)“距離目的節(jié)點的距離的遠近”定義了不同的優(yōu)先級區(qū)域，從而設計出了基于優(yōu)先級的競爭轉(zhuǎn)發(fā)機制:各個節(jié)點根據(jù)距離值在不同的時刻回復允許發(fā)送(clear to send，CTS)，距離值越小的節(jié)點優(yōu)先級越高，越快回復CTS，從而競爭得到轉(zhuǎn)發(fā)機會。而且，它規(guī)定了相對復雜的握手動作用于避免候選節(jié)點之間的沖突。文獻［7-8，11-12］已經(jīng)證明了機會路由協(xié)議GeRaF(geographic random forwarding)擁有比傳統(tǒng)路由協(xié)議更好的時延和吞吐量性能。然而在這樣的貪婪轉(zhuǎn)發(fā)策略中，候選中繼節(jié)點僅僅根據(jù)當前本地節(jié)點的情況判斷自己是否應承接此次轉(zhuǎn)發(fā)，那么即使在一個連通的網(wǎng)絡中也會出現(xiàn)這樣的問題:經(jīng)過某節(jié)點轉(zhuǎn)發(fā)之后的若干跳內(nèi)，沒有可用的后續(xù)節(jié)點能轉(zhuǎn)發(fā)當前的數(shù)據(jù)報文。因此網(wǎng)絡的成功傳輸率會減小，尤其是在某些有障礙物的場景中或網(wǎng)絡節(jié)點密度較低的場景中。

本文中我們提出了一種新的轉(zhuǎn)發(fā)策略:機會路由中考慮后續(xù)路徑的轉(zhuǎn)發(fā)策略(selection considering future path，CFP)。在CFP中，節(jié)點會考慮某一跳之后若干跳的傳輸情況，從而做出是否應該參與轉(zhuǎn)發(fā)此數(shù)據(jù)報文的決定。

1 問題描述

前面提到了在貪婪轉(zhuǎn)發(fā)策略中，后續(xù)路徑中可能會出現(xiàn)沒有轉(zhuǎn)發(fā)節(jié)點可用的情況，其原因是:當前轉(zhuǎn)發(fā)節(jié)點的鄰居節(jié)點中距離目的節(jié)點最近的點，它成功收到了當前轉(zhuǎn)發(fā)節(jié)點轉(zhuǎn)發(fā)的數(shù)據(jù)報文，然而它沒有比其距離目的節(jié)點更近的鄰居節(jié)點。即使這個節(jié)點仍然擁有比其距離目的節(jié)點更近的鄰居節(jié)點，那么經(jīng)過此點轉(zhuǎn)發(fā)后，在若干跳中，仍然有可能會出現(xiàn)類似的情況。

如圖1所示，假設節(jié)點傳輸半徑為R，源節(jié)點是S，目的節(jié)點是D。根據(jù)貪婪轉(zhuǎn)發(fā)策略，N0是S點距離目的節(jié)點最近的一個點，它將有最大可能獲得轉(zhuǎn)發(fā)的機會。此跳之后，N1和N2都是當前轉(zhuǎn)發(fā)節(jié)點N0的鄰居節(jié)點，而且他們距離目的節(jié)點相對N0更近，他們將競爭獲得此跳的轉(zhuǎn)發(fā)權(quán)。N1是N0所有鄰居中距離目的節(jié)點最近的節(jié)點，它將有最高的優(yōu)先級贏得此次轉(zhuǎn)發(fā)。然而，如果N1得到了轉(zhuǎn)發(fā)的機會，那么就會出現(xiàn)上述問題:N1的鄰居節(jié)點中，沒有比其距離目的節(jié)點更近的鄰居節(jié)點可用來進行轉(zhuǎn)發(fā)。實際上在基于貪婪轉(zhuǎn)發(fā)策略的GeRaF中，當N1嘗試著發(fā)了若干次請求發(fā)送(request to send，RTS)之后，如果沒有收到候選節(jié)點返回的CTS，它將丟棄此次傳輸?shù)臄?shù)據(jù)報文。然而，如果N2得到了轉(zhuǎn)發(fā)機會的話，那么通過N2-N3-N4，目的節(jié)點是能夠接收到這個數(shù)據(jù)報文的。N1就是一個“似乎可以勝任轉(zhuǎn)發(fā)任務”的節(jié)點。如果這樣的節(jié)點獲得了轉(zhuǎn)發(fā)的機會，那么實際上數(shù)據(jù)報文是有很大可能不能成功到達目的節(jié)點。

圖1 中繼節(jié)點選取示意圖Fig.1 Relay node selection example

2 考慮后續(xù)路徑的轉(zhuǎn)發(fā)策略

2.1 考慮后續(xù)路徑的轉(zhuǎn)發(fā)策略的基本思想

CFP的基本思想如下:首先確定候選節(jié)點，接著對候選節(jié)點進行后續(xù)路徑檢測，以確定合格的候選節(jié)點，最后合格的候選節(jié)點競爭發(fā)送CTS。當一個節(jié)點接收到RTS的時候，首先確定自己是否是一個候選節(jié)點，如果某節(jié)點是候選節(jié)點，那么該節(jié)點才對自己進行后續(xù)路徑檢測，否則此節(jié)點不發(fā)送CTS。候選節(jié)點的確定包括3個條件，全部滿足則是候選節(jié)點，設當前轉(zhuǎn)發(fā)節(jié)點為CN，那么這3個條件可表示為:1)是CN的鄰居節(jié)點;2)和目的節(jié)點的距離較CN而言更近;3)不是CN上一跳節(jié)點的鄰居節(jié)點。前2個條件是貪婪轉(zhuǎn)發(fā)策略中判斷是否是候選中繼節(jié)點的條件，而第3個條件則是為了防止在機會路由中出現(xiàn)傳輸死循環(huán)式。如果候選節(jié)點不存在，那么將沒有CTS回復到CN，CN將暫時緩存此數(shù)據(jù)報文，等待一段時間之后再次發(fā)送RTS。若CN對同一數(shù)據(jù)報文發(fā)送了指定次數(shù)的RTS都沒有得到回復，那么CN放棄此數(shù)據(jù)報文。

如果這樣的候選節(jié)點存在，那么此候選節(jié)點在本地范圍內(nèi)被標記為當前轉(zhuǎn)發(fā)節(jié)點的下一跳候選節(jié)點(設為FN1)。FN1接著開始進行后續(xù)路徑的檢測，估計通過此FN1是否能夠使得此數(shù)據(jù)報文到達最終目的節(jié)點。FN1用其鄰居節(jié)點的地理位置信息作檢測，檢測的方法和上述類似，搜索FN1的鄰居節(jié)點中是否存在一個適合進行接下來第二跳轉(zhuǎn)發(fā)的節(jié)點FN2，F(xiàn)N2需要滿足的條件表述為:1)是FN1的鄰居節(jié)點;2)和目的節(jié)點的距離較FN1而言更近且是FN1鄰居節(jié)點中距目的節(jié)點最近的一個點;3)不是CN的鄰居節(jié)點。選中FN2之后，在FN1本地節(jié)點范圍內(nèi)繼續(xù)搜索是否存在FN3，接著搜索 FN4，F(xiàn)N5，…，這樣的檢測模式類似于一個嵌套搜索的過程。設FNK為第K－1次后續(xù)搜索所得的候選節(jié)點，當目的節(jié)點在 FNK傳輸范圍內(nèi)時，或者當FN(K+1)不存在時，檢測結(jié)束。前一種檢測結(jié)果表明通過本候選節(jié)點FN1的轉(zhuǎn)發(fā)，該數(shù)據(jù)報文能夠到達目的節(jié)點;后一種檢測結(jié)果表明無法到達目的節(jié)點。若檢測得出可以到達目的節(jié)點，那么此候選節(jié)點參與發(fā)送CTS的競爭，否則退出此次轉(zhuǎn)發(fā)。如圖1所示，當N1接收到RTS時，根據(jù)CFP，它能得出自己是候選節(jié)點，然而在第一輪搜索時就不能找到FN1，因此檢測結(jié)果為N1不能參與轉(zhuǎn)發(fā)的競爭。然而N2可以檢測到如果自己拿到轉(zhuǎn)發(fā)機會，能夠使得數(shù)據(jù)報文成功到達目的節(jié)點D，于是N2參與轉(zhuǎn)發(fā)，通過接下來的N3-N4，數(shù)據(jù)報文就到達了D。

候選節(jié)點競爭轉(zhuǎn)發(fā)數(shù)據(jù)報文的過程和貪婪轉(zhuǎn)發(fā)策略類似:根據(jù)和目的節(jié)點距離的大小劃分發(fā)送CTS的時間優(yōu)先級，距離目的節(jié)點更近的節(jié)點更早地給CN回復CTS，如果多個CTS沖突，那么發(fā)送CTS的候選節(jié)點采用隨機時間等待的退避算法隨機等待一段時間之后再重發(fā)CTS，保證只有一個CTS到達當前轉(zhuǎn)發(fā)節(jié)點。

2.2 CFP 轉(zhuǎn)發(fā)策略

考慮節(jié)點的移動性，將會有另外一個問題，如圖2所示，目的節(jié)點在N1收到N0所發(fā)的RTS時處于D1的位置，此時N1能夠參與競爭并且可以獲得轉(zhuǎn)發(fā)權(quán)。然而當N1接收完數(shù)據(jù)報文準備發(fā)送RTS時，目的節(jié)點從D1移動到了D2的位置，于是當N1發(fā)送了幾次RTS之后，沒有CTS回復，N1就丟棄了這個數(shù)據(jù)報文。同樣，在圖1中，如果N1需要傳輸一個自己產(chǎn)生的數(shù)據(jù)報文給D，那么也是無法實現(xiàn)的。為了使這些數(shù)據(jù)報文能夠成功傳輸出去，CFP

圖2 考慮移動性的中繼節(jié)點選取示意圖Fig.2 Example of relay node selection with node mobility

選取候選節(jié)點:當一個節(jié)點收到RTS以后，它首先檢測CN其本身是否是一個合格的候選節(jié)點，檢測過程和前述方法類似，估計經(jīng)CN轉(zhuǎn)發(fā)之后通過一系列FN的傳輸，是否能使得數(shù)據(jù)報文成功到達目的節(jié)點。如果檢測到通過CN轉(zhuǎn)發(fā)數(shù)據(jù)報文可以到達目的節(jié)點，那么本節(jié)點執(zhí)行前述CFP的3個過程;如果檢測得到通過CN轉(zhuǎn)發(fā)數(shù)據(jù)報文無法到達目的節(jié)點，那么無論本節(jié)點是否執(zhí)行CFP的3個過程的第一個過程，即無論自己是否是候選節(jié)點，它都立刻對自己進行后續(xù)路徑檢測，如果本節(jié)點依照CFP的后2步的檢測，得出自己可以連通到目的節(jié)點，那么本節(jié)點參與競爭發(fā)送CTS。綜上所述，整個CFP的執(zhí)行過程如下:首先檢測CN是否是合格的候選節(jié)點，如果是，那么按照確認候選節(jié)點—后續(xù)路徑檢測—競爭發(fā)送CTS這3個步驟順序執(zhí)行;如果CN不是合格的候選節(jié)點，那么按照后續(xù)路徑檢測—競爭發(fā)送CTS這2個步驟實現(xiàn)下一跳中繼節(jié)點的選取。

2.3 采用CFP的機會路由數(shù)據(jù)成功傳輸率的分析

首先考慮單次報文傳輸成功接收概率密度是發(fā)射機距離的函數(shù)，此函數(shù)可通過(1)式計算得到［7-8，13］

(1)式中:ψ為SNR;ptx與pnoise為發(fā)射機功率和噪聲功率;α為路徑損耗指數(shù);σ為接收信號強度概率分布的標準方差。假設網(wǎng)絡中的節(jié)點服從均勻分布且最大傳輸半徑為R，那么如圖3所示，對于單跳傳輸而言，由文獻［8］可得傳輸區(qū)域中能夠成功接收點S發(fā)送的數(shù)據(jù)報文的概率為

(2)式中:A(x)為陰影面積;A(0)為近似的有效傳輸區(qū)域;IN(x)是一個基本表達式的符號，詳細意義參考文獻［7-8］。

圖3描述了移動自組織網(wǎng)絡的傳遞過程和子分區(qū)示意圖。圖3b中，A(0)分成N個子區(qū)域，其中ri－1和ri分別是第i個子區(qū)域的內(nèi)外圓半徑。

圖3 移動自組織網(wǎng)絡的傳遞過程和子分區(qū)示意圖Fig.3 Transmission progress in MANET and subdividing into sub-sectors

由文獻［8］可得，當N趨向于無窮大時，I∞(x)計算如下

假設S為網(wǎng)絡面積大小，網(wǎng)絡中節(jié)點數(shù)目為Nd，那么對于發(fā)送節(jié)點而言，有效傳輸區(qū)域中至少有一個節(jié)點能夠執(zhí)行下一跳的概率為

(4)式中，pr為傳輸區(qū)域中能夠成功接收點S發(fā)送的數(shù)據(jù)報文的概率。

根據(jù)文獻［14］，我們可設每次傳輸距離目的節(jié)點的平均前進距離為rpg，平均每個業(yè)務數(shù)據(jù)報文需要途經(jīng)的距離為d，那么平均跳數(shù)為

(5)式中，int(x)是x的取整運算。那么輕業(yè)務負載下GeRaF的成功傳輸概率為

其因為沒有后續(xù)中繼節(jié)點而導致的失敗概率為

若網(wǎng)絡是連通的，那么因為沒有后續(xù)中繼節(jié)點而導致的失敗傳輸可以被挽救回來，因此其成功傳輸?shù)母怕蚀蠹s為

由此可見，使用CFP的機會路由能有效減小數(shù)據(jù)報文傳輸失敗的概率，由此可提高系統(tǒng)的成功傳輸率和吞吐率，這點將在后面的仿真結(jié)果中被證明。

3 仿真結(jié)果

我們選擇GeRaF作為機會路由協(xié)議，因為它是現(xiàn)在機會路由協(xié)議中最完善的一個協(xié)議。仿真使用OPNET仿真平臺，且網(wǎng)絡中所有節(jié)點均可產(chǎn)生業(yè)務，轉(zhuǎn)發(fā)業(yè)務和接收業(yè)務，仿真參數(shù)如表1所示。

表1 仿真參數(shù)Tab.1 Simulation parameters

仿真時主要考慮3個性能:數(shù)據(jù)報文成功傳輸概率(ratio)，實際吞吐率(goodput)和時延(delay)。數(shù)據(jù)報文成功傳輸概率是指網(wǎng)絡中所有節(jié)點成功接收到的數(shù)據(jù)報文數(shù)目和產(chǎn)生數(shù)據(jù)報文總數(shù)目的比值;實際吞吐率是指整個網(wǎng)絡平均每秒接收到的比特數(shù);時延是數(shù)據(jù)報文的端到端平均時延。

圖4所示為數(shù)據(jù)報文成功傳輸率的仿真結(jié)果。從圖4中可以看出，CFP在成功傳輸率性能上明顯優(yōu)于貪婪轉(zhuǎn)發(fā)策略。尤其是在節(jié)點密度較低的網(wǎng)絡中，此優(yōu)勢更加明顯，在網(wǎng)絡尺寸一定而網(wǎng)絡節(jié)點數(shù)目只有30時，CFP可以提升大概20%的成功傳輸率性能。原因是，當網(wǎng)絡節(jié)點密度較小時，出現(xiàn)沒有后續(xù)中繼節(jié)點的可能性更大，因為上述pr值更低。當全網(wǎng)節(jié)點均可移動時，網(wǎng)絡的數(shù)據(jù)成功傳輸率僅比靜態(tài)的網(wǎng)絡略低，其原因是，CFP針對節(jié)點的移動性專門做了一次后續(xù)檢測，即前述CFP的第一步。通過這樣的一步檢測，能夠針對上一跳節(jié)點在發(fā)送數(shù)據(jù)前后位置的變化，在選擇下一跳中繼節(jié)點時做出不同的選擇，避免了數(shù)據(jù)報文因節(jié)點移動性造成的丟失。因此該轉(zhuǎn)發(fā)策略非常適用于節(jié)點可移動的網(wǎng)絡。

圖4 數(shù)據(jù)報文成功傳輸概率仿真結(jié)果對比示意圖Fig.4 Performance of successful delivery ratio

圖5所示為實際吞吐率的仿真結(jié)果，由于數(shù)據(jù)報文成功傳輸率增大，相應地，實際接收到的比特數(shù)也增大。

圖5 實際吞吐率仿真結(jié)果對比示意圖Fig.5 Performance of goodput

圖6所示為時延仿真結(jié)果對比示意圖。使用貪婪轉(zhuǎn)發(fā)策略的機會路由總是搜索距離目的節(jié)點最近的點進行中繼，而CFP不是這樣的貪婪策略，因此一個數(shù)據(jù)報文實際傳送的距離可能會大于貪婪轉(zhuǎn)發(fā)策略，平均跳數(shù)也可能大于貪婪轉(zhuǎn)發(fā)策略。因此，時延稍微高一點是可以理解的。從上述結(jié)果可以看出，對比貪婪轉(zhuǎn)發(fā)策略，雖然CFP在時延性能上稍有犧牲，然而在數(shù)據(jù)報文成功傳輸率和實際吞吐率性能上，CFP優(yōu)于貪婪轉(zhuǎn)發(fā)策略。

圖6 時延仿真結(jié)果對比示意圖Fig.6 Performance of delay

4 結(jié)束語

本文中我們針對在移動Ad Hoc網(wǎng)絡中使用機會路由協(xié)議時，采用貪婪轉(zhuǎn)發(fā)策略會引起“沒有后續(xù)轉(zhuǎn)發(fā)節(jié)點”這一現(xiàn)象，提出了一種新的應用于移動Ad Hoc網(wǎng)絡的機會路由轉(zhuǎn)發(fā)策略—考慮后續(xù)路徑的轉(zhuǎn)發(fā)策略(CFP)。其主要思想是在每跳之后進行中繼節(jié)點選取時，不僅考慮各個候選節(jié)點本身距離目的節(jié)點的距離，還要考慮經(jīng)過此節(jié)點的轉(zhuǎn)發(fā)，當前數(shù)據(jù)報文能否成功到達目的節(jié)點。仿真結(jié)果表明，對比于采用貪婪轉(zhuǎn)發(fā)策略選取中繼節(jié)點的機會路由協(xié)議GeRaF，CFP在少量增加數(shù)據(jù)傳輸平均時延的情況下，能夠有效地消除無后續(xù)轉(zhuǎn)發(fā)節(jié)點的現(xiàn)象，提高了數(shù)據(jù)傳送成功率和網(wǎng)絡吞吐率，提高了可靠性。

［1］JOHNSON David B，MALTZ David A，BROCH Josh.DSR:The dynamic source routing protocol for multihop wireless ad hoc networks［C］//ACM/IEEE.Ad Hoc Networking.USA:Addison Wesley Longman Publishing Co，2001:139-172.

［2］PERKINS C E，ROYER E M.Ad hoc on-demand distance vector routing［C］//IEEE WORKSHOP.Proc of the 2nd IEEE Workshop on Mobile Computing Systems and Applications.USA:IEEE Computer Society，1999:90.

［3］SONG Li-bo，KOTZ David F.Evaluating Opportunistic Routing Protocols with Large Realistic Contact Traces ［C］//ACM，SIGCOM.Proceedings of the second ACM workshop on Challenged networks.USA:ACM，2007:35-42.

［4］COUTO D S J De，AGUAYO D，BICKET J，et al.A high throughput path metric for multi-hop wireless routing［J］.Wireless Networks，2003，11(4):419-434.

［5］BISWAS S，MORRIS R.Opportunistic Routing in Multihop Wireless Networks［J］.ACM SIGCOMM Computer Communication Review，2004，34(1):69-74.

［6］邵凱，張紅衛(wèi)，梁燕，等.無線傳感網(wǎng)絡中的數(shù)據(jù)融合問題［J］.重慶郵電大學學報(自然科學版)，2006，18(1):53-59.

［7］ZORZI M，RAO R R.Geographic Random Forwarding(GeRaF)for Ad Hoc and Sensor Networks:Multihop Performance ［J］.IEEE Trans:Mobile Computing，2003，2(4):337-348.

［8］ZORZI M，RAO R R.Geographic random forwarding(GeR-aF)for ad hoc and sensor networks:energy and latency performance ［J］.Mobile Computing，2003，2(4):349-365.

［9］JUANG P，OKI H，WANG Y，et al.Rubenstein.Energy-EfficientComputing for Wildlife Tracking:Design Tradeoffs and Early Experiences with ZebraNet［J］.ACM SIGPLAN Notices，2002，37(10):96-107.

［10］BISWAS S，MORRIS R.ExOR:Opportunistic routing in multi-hop wireless networks［J］.ACM SIGCOMM Computer Communication Review，2005，35(4):133-144.

［11］KARP B.Geographic routing for wireless networks［D］.USA:Harvard University，2000.

［12］ROZNER Eric，SESHADRI Jayesh，MEHTA Yogita，et al.Simple Opportunistic Routing Protocol for Wireless Mesh Networks［C］//WiMesh 2006.USA:2nd IEEE Workshop，2006:48-54.

［13］LUK Chun Pong，LAU Wing Cheong，YUE On Ching.An Analysis of Opportunistic Routing in Wireles Mesh Network［C］//IEEE explore.ICC 2008 proceedings.China:IEEE International Conference ，2008:2877-2883.

［14］ZHONG Zi-fei，NELAKUDITI Srihari.On the Efficacy of Opportunistic Routing［C］//IEEE WORKSHOP.Secom’07.San Diego:4th Annual IEEE Com-munications Society Conference，2007:441-450.