聶 骕

(上海海事大學(xué) 商船學(xué)院，中國(guó) 上海 201306)

0 引言

無(wú)線傳感網(wǎng)是由許多低功耗的傳感器節(jié)點(diǎn)組成的，它們通常具有感知、計(jì)算、通信能力?，F(xiàn)階段的研究多數(shù)是靜態(tài)的無(wú)線傳感網(wǎng)，如森林防火、建筑監(jiān)控、地標(biāo)檢測(cè)等等，這樣的應(yīng)用環(huán)境中，網(wǎng)絡(luò)比較穩(wěn)定，傳感器節(jié)點(diǎn)基本沒(méi)有拓?fù)渥兓虼吮阌谶\(yùn)用，且網(wǎng)絡(luò)效率較高。而在有的應(yīng)用領(lǐng)域，如海上搜救等重要領(lǐng)域，應(yīng)用環(huán)境比較惡劣，常常由于海上各種客觀因素，包括風(fēng)壓、海流、大風(fēng)大浪的影響，網(wǎng)絡(luò)信道質(zhì)量通常較差，節(jié)點(diǎn)之間并不是總存在一條可達(dá)路徑，因此傳統(tǒng)的路由并不適合于類(lèi)似海上的惡劣環(huán)境。

因此，本文針對(duì)近年，對(duì)于無(wú)線傳感網(wǎng)（WSN）的研究現(xiàn)在正不斷的增長(zhǎng)，在Ad hoc 無(wú)線網(wǎng)中，資源限制一直是重要而又難以解決的問(wèn)題。機(jī)會(huì)路由的提出，有效的改善了這些問(wèn)題。機(jī)會(huì)路由通過(guò)充分利用無(wú)線信道的廣播特性，可以大大提高無(wú)線多跳網(wǎng)絡(luò)的性能。因此，自從機(jī)會(huì)路由被提出后，也成為了各個(gè)研究機(jī)構(gòu)的研究熱點(diǎn)?，F(xiàn)在的一些路由方案，都是采用ETX 當(dāng)路由判據(jù)，ETX 的獲取需要周期性地發(fā)送探測(cè)包，路由的開(kāi)銷(xiāo)很大。

最具有代表性的機(jī)會(huì)路由協(xié)議有ExOR[1]，SAOR[3]。但是它們都有很大的改進(jìn)空間，如ExOR 存在數(shù)據(jù)包傳輸效率不高，可擴(kuò)展性不強(qiáng)等問(wèn)題。傳統(tǒng)的路由模式是：在端到端數(shù)據(jù)包傳送過(guò)程中，先建立一條端到端的節(jié)點(diǎn)序列，然后在每次分組轉(zhuǎn)發(fā)時(shí)，已經(jīng)下一跳的節(jié)點(diǎn)，開(kāi)始執(zhí)行鏈路層數(shù)據(jù)的轉(zhuǎn)發(fā)。因此一旦傳送過(guò)程有分組丟失或者錯(cuò)誤，那么就要重新啟動(dòng)鏈路層開(kāi)始從頭再來(lái)。所以可以看出，在鏈路質(zhì)量和穩(wěn)定性較差的環(huán)境下，頻繁的鏈路層數(shù)據(jù)重傳將消耗大量的帶寬資源。因此，盡管確定性路由方式邏輯簡(jiǎn)單，但未能充分考慮無(wú)線信道的廣播特性、時(shí)變特性和干擾不規(guī)則性。無(wú)線信道的廣播特性使得一次分組轉(zhuǎn)發(fā)可能被多個(gè)節(jié)點(diǎn)收到，且接收概率各不相同；無(wú)線鏈路的時(shí)變特性導(dǎo)致網(wǎng)絡(luò)中鏈路的狀態(tài)隨時(shí)間而改變。路由協(xié)議設(shè)計(jì)過(guò)程中如果缺乏對(duì)信道廣播和丟失特性的充分考慮，必將導(dǎo)致大量網(wǎng)絡(luò)資源無(wú)謂浪費(fèi)，這將嚴(yán)重影響無(wú)線多跳網(wǎng)絡(luò)的吞吐量和提供服務(wù)質(zhì)量的能力。

1 機(jī)會(huì)主義路由工作機(jī)理

機(jī)會(huì)主義路由(Opportunistic outing)是一種后擇路由，節(jié)點(diǎn)在轉(zhuǎn)發(fā)包時(shí)不以源-目標(biāo)節(jié)點(diǎn)間直接可達(dá)路徑為基礎(chǔ)，而是將報(bào)文廣播出去后，再利用轉(zhuǎn)發(fā)候選集中的最佳節(jié)點(diǎn)來(lái)轉(zhuǎn)發(fā)報(bào)文。充分利用無(wú)線信道的廣播特性，機(jī)會(huì)性的選擇報(bào)文能到達(dá)的最佳節(jié)點(diǎn)轉(zhuǎn)發(fā)，盡可能地克服動(dòng)態(tài)拓?fù)?、鏈路信道變化頻繁等影響，從而有效提高無(wú)線網(wǎng)絡(luò)性能。不先確定下一跳節(jié)點(diǎn)，這樣可以選擇最佳的節(jié)點(diǎn)來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)包。假設(shè)源節(jié)點(diǎn)要廣播數(shù)據(jù)包，那么監(jiān)聽(tīng)到這個(gè)數(shù)據(jù)包的鄰居節(jié)點(diǎn)組成一個(gè)轉(zhuǎn)發(fā)節(jié)點(diǎn)列表，每次傳輸都以最佳節(jié)點(diǎn)（如離目標(biāo)節(jié)點(diǎn)最近，或開(kāi)銷(xiāo)最?。﹣?lái)轉(zhuǎn)發(fā)報(bào)文。

路由是在網(wǎng)絡(luò)數(shù)據(jù)通信系統(tǒng)的一個(gè)重要的要求。有路由協(xié)議所需要的三個(gè)主要組成部分：一個(gè)目的地的規(guī)范，路由目標(biāo)和策略路由。大多數(shù)路由協(xié)議是基于一個(gè)固定的目標(biāo)規(guī)范，路由目標(biāo)和路由策略往往遵循分層計(jì)劃。有兩種通用的有線網(wǎng)絡(luò)和無(wú)線網(wǎng)絡(luò)中的最短路徑（或最低的成本）的路由范例通常被采用，一是在一個(gè)單一的任何源-目的對(duì)之間的最短路徑的計(jì)算。這被稱(chēng)為隱式應(yīng)答路由。在無(wú)線傳感器網(wǎng)絡(luò)中，要考慮到具有挑戰(zhàn)性的環(huán)境中的資源約束和頻繁的干擾和節(jié)點(diǎn)故障，路由無(wú)線傳感器網(wǎng)絡(luò)必須精心設(shè)計(jì)和優(yōu)化-理想與本地適應(yīng)能力的數(shù)據(jù)傳輸速率和網(wǎng)絡(luò)條件的變化。此外，一個(gè)典型的無(wú)線傳感器網(wǎng)絡(luò)中的通信模式，要包括傳感器和接收器節(jié)點(diǎn)布置。

已經(jīng)有一些關(guān)于OR 的改進(jìn)的變種，采取機(jī)會(huì)主義傳輸?shù)母拍盍死脽o(wú)線網(wǎng)絡(luò)的時(shí)空多樣性。在一般情況下都是采用以下兩種常見(jiàn)的方法：

i)隨機(jī)無(wú)限制的CR

ii)先決和限制的CR

第一種類(lèi)型中，能源是不是一個(gè)主要的問(wèn)題，而第二種類(lèi)型是以確保潛在的中繼節(jié)點(diǎn)參與形成源目標(biāo)路徑在能源效率方面具有最大的潛在回報(bào)為目的。

第一個(gè)可供選擇的潛在的中繼節(jié)點(diǎn)只需要一個(gè)最小的初始化時(shí)間，第二個(gè)版本是需要額外的初始化時(shí)間來(lái)確定的，可用于對(duì)每次發(fā)送的每個(gè)中繼節(jié)點(diǎn)組。由于其在無(wú)線傳感器網(wǎng)絡(luò)中的潛在用途，這個(gè)版本將本文中詳細(xì)探討。

OR 協(xié)議程序的重要方面之一是每個(gè)節(jié)點(diǎn)的潛在中繼之間的協(xié)調(diào)。下面將會(huì)講到自適應(yīng)機(jī)會(huì)路由的具體描述。

2 自適應(yīng)機(jī)會(huì)路由的具體描述

自適應(yīng)機(jī)會(huì)路由其性能取決于幾個(gè)重要因素：候選轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇；候選節(jié)點(diǎn)的優(yōu)先級(jí)；候選節(jié)點(diǎn)之間的協(xié)調(diào)。

2.1 候選轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇

由于無(wú)線網(wǎng)絡(luò)的性質(zhì)，每次傳輸，在默認(rèn)情況下，都被當(dāng)做是一個(gè)廣播操作。傳輸范圍內(nèi)的所有節(jié)點(diǎn)可以監(jiān)聽(tīng)消息，并實(shí)現(xiàn)了不同的數(shù)據(jù)包的接收率。此外，最近的研究表明，除了有被“連接”和“斷開(kāi)”地區(qū)，許多環(huán)節(jié)都在一個(gè)區(qū)域內(nèi)被稱(chēng)為“過(guò)渡區(qū)”，實(shí)際上，它們可能具有最高的能源效率。然而，為了確保每個(gè)傳輸?shù)哪芰?，可靠性和?zhǔn)確性方面是有效的，必須設(shè)計(jì)挑選出來(lái)一個(gè)適當(dāng)?shù)亩攘?。這個(gè)度量必須確保只有相關(guān)的節(jié)點(diǎn)都參與或考慮在每次傳輸。理想的情況下，該指標(biāo)應(yīng)共同考慮幾個(gè)因素，如數(shù)據(jù)包接收率，距離，數(shù)據(jù)包轉(zhuǎn)發(fā)時(shí)間和跳步。

選擇過(guò)程的主要目的是確定候選中繼節(jié)點(diǎn)的集合，給出一個(gè)最優(yōu)的數(shù)據(jù)包轉(zhuǎn)發(fā)效率。分析涉及的候選節(jié)點(diǎn)在設(shè)置平衡時(shí)需要仔細(xì)分析。有許多候選集合中的中繼，往往導(dǎo)致在減少成本的轉(zhuǎn)發(fā)。然而，一些鄰居不取得進(jìn)展如預(yù)期前往目的地。此外，在一個(gè)密集的網(wǎng)絡(luò)，由于冗余傳輸，越來(lái)越多的候選節(jié)點(diǎn)有可能增加開(kāi)銷(xiāo)，以及導(dǎo)致能源利用效率低下。

2.2 候選節(jié)點(diǎn)的優(yōu)先級(jí)設(shè)置

在決定中了候選中繼（CRS）的節(jié)點(diǎn)的數(shù)量之后，下一個(gè)問(wèn)題是根據(jù)優(yōu)先順序排列這些節(jié)點(diǎn)。這個(gè)排名為每個(gè)傳輸?shù)淖畲蠡蜃钚』峁┮粋€(gè)是很重要的客觀標(biāo)準(zhǔn)，如是壽命，延遲和吞吐量。同樣重要的是被選擇的節(jié)點(diǎn)的CRS，要提高可靠性的每個(gè)傳輸之間的協(xié)調(diào)。理想情況下，將被用于計(jì)算每個(gè)候選的優(yōu)先級(jí)度量的屬性必須反映了鏈路，距離，和能量水平等條件。

這里，我們?cè)O(shè)置一個(gè)無(wú)序的節(jié)點(diǎn)集V，v∈（1，n）的整數(shù)，v 為節(jié)點(diǎn)，假設(shè)這些節(jié)點(diǎn)有有限的隊(duì)列緩沖器，此外知道他們自己的位置，以及鄰居節(jié)點(diǎn)的位置以及目標(biāo)節(jié)點(diǎn)的信息。在OR 里，每個(gè)節(jié)點(diǎn)v 將選擇候選節(jié)點(diǎn)并且列出優(yōu)先級(jí)來(lái)轉(zhuǎn)發(fā)它的數(shù)據(jù)包到目的節(jié)點(diǎn)。因此，這些節(jié)點(diǎn)應(yīng)該以要是監(jiān)聽(tīng)到源節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包信息的節(jié)點(diǎn)，二還得是根據(jù)鏈路信息質(zhì)量，距目的節(jié)點(diǎn)的距離較近并且能夠聯(lián)系到目標(biāo)節(jié)點(diǎn)的節(jié)點(diǎn)。（即圖1 中的重疊陰影區(qū)所包含的節(jié)點(diǎn)）

圖1

為了考慮將節(jié)點(diǎn)的失敗考慮進(jìn)去，我們要設(shè)定一個(gè)延遲時(shí)間T，如果第一個(gè)最佳候選節(jié)點(diǎn)沒(méi)有轉(zhuǎn)發(fā)成功，在T 時(shí)間之后，最佳候選節(jié)點(diǎn)列表里的第二個(gè)節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，如此直到目的節(jié)點(diǎn)收到數(shù)據(jù)包。所以總體上說(shuō)，一個(gè)節(jié)點(diǎn)的優(yōu)先級(jí)越高，它等待轉(zhuǎn)發(fā)數(shù)據(jù)包的時(shí)間越短。當(dāng)節(jié)點(diǎn)等待輪到它轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)，如果節(jié)點(diǎn)收到一個(gè)更高優(yōu)先級(jí)節(jié)點(diǎn)告訴它數(shù)據(jù)包已經(jīng)被發(fā)送的消息時(shí)，它將丟棄那個(gè)數(shù)據(jù)包。這就是隱式應(yīng)答程序，它對(duì)消除數(shù)據(jù)包被多重轉(zhuǎn)發(fā)有重要的作用，同時(shí)也減少?zèng)_突和中斷。隱式應(yīng)答程序機(jī)制的主要優(yōu)勢(shì)是不需要一個(gè)精確的數(shù)據(jù)包應(yīng)答，因此也節(jié)省了能量。

2.3 候選節(jié)點(diǎn)的協(xié)調(diào)

由于需要處理中的多個(gè)節(jié)點(diǎn)的CRS 的潛在需要，在這些節(jié)點(diǎn)之間的協(xié)調(diào)非常重要，基本上在MAC 層進(jìn)行協(xié)調(diào)。協(xié)調(diào)這些節(jié)點(diǎn)的主要目的是為了防止重復(fù)的數(shù)據(jù)包轉(zhuǎn)發(fā)到目的地，也承認(rèn)包接收成功的可靠性的目的。這些節(jié)點(diǎn)的協(xié)調(diào)途徑之一涉及附加為每個(gè)CRS 候選的優(yōu)先級(jí)信息，然后發(fā)送它的開(kāi)銷(xiāo)。這樣，在CRS 中的每個(gè)節(jié)點(diǎn)將了解的其他節(jié)點(diǎn)的優(yōu)先級(jí)。根據(jù)此信息，候選節(jié)點(diǎn)的調(diào)度，可以進(jìn)行避免碰撞和減少交通堵塞的目的，一個(gè)隱含的確認(rèn)數(shù)據(jù)包可以被發(fā)送到發(fā)送方。整體實(shí)施的協(xié)調(diào)機(jī)制也較難，因?yàn)閼?yīng)答程序也受無(wú)線網(wǎng)絡(luò)環(huán)境的影響。一個(gè)強(qiáng)大的機(jī)會(huì)路由機(jī)制是以確保采用高增益無(wú)線傳感器網(wǎng)絡(luò)受青睞的。

3 總結(jié)

本文提出了一個(gè)關(guān)于改進(jìn)機(jī)會(huì)路由主義的建議，是根據(jù)每個(gè)節(jié)點(diǎn)的不同情況做出自適應(yīng)反應(yīng)，盡量讓數(shù)據(jù)包能成功傳輸?shù)侥康墓?jié)點(diǎn)。它利用現(xiàn)有的隱式應(yīng)答程序來(lái)決定節(jié)點(diǎn)與其他所有節(jié)點(diǎn)之間的關(guān)系，這個(gè)加強(qiáng)策略對(duì)于端到端延遲，數(shù)據(jù)包傳輸率及能效都會(huì)有比較好的效果。當(dāng)然只是初步建議，如未來(lái)有具體仿真是更好。

［1］S.Biswas and R.Morris.ExOR:Opportunistic Multi-Hop Routing for Wireless Networks[C]//SIGCOMM.,2005.

［2］H.Dubois-Ferriere,M.Grossglauser,and M.Vetterli.Leastcost Opportunistic Routing [C]//45th Proceedings of the Allerton Conference on Communication,Control and Computing,2007.

［3］Bejerano Y,Breitbart Y,Garofalakis M,et al.Physical Topology Discovery for Large Multi-subnet Networks [C]//Proceedings of IEEE INFOCOM’03.New York,USA:IEEE Press,2003:342-352.

［4］梁紹芳，武穆清，甄巖.適用于多跳無(wú)線網(wǎng)絡(luò)的機(jī)會(huì)路由機(jī)制[J].計(jì)算機(jī)工程，2010，19(36)：137-141.