WSN中的自適應(yīng)機會路由

聶 骕

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

0 引言

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

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

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

1 機會主義路由工作機理

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

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

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

i)隨機無限制的CR

ii)先決和限制的CR

第一種類型中，能源是不是一個主要的問題，而第二種類型是以確保潛在的中繼節(jié)點參與形成源目標路徑在能源效率方面具有最大的潛在回報為目的。

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

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

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

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

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

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

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

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

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

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

圖1

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

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

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

3 總結(jié)

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

［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ǎng)絡(luò)的機會路由機制[J].計算機工程，2010，19(36)：137-141.