WSN中的自適應機會路由

聶 骕

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

0 引言

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

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

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

1 機會主義路由工作機理

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

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

已經有一些關于OR 的改進的變種，采取機會主義傳輸的概念了利用無線網絡的時空多樣性。在一般情況下都是采用以下兩種常見的方法：

i)隨機無限制的CR

ii)先決和限制的CR

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

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

OR 協議程序的重要方面之一是每個節點的潛在中繼之間的協調。下面將會講到自適應機會路由的具體描述。

2 自適應機會路由的具體描述

自適應機會路由其性能取決于幾個重要因素：候選轉發節點的選擇；候選節點的優先級；候選節點之間的協調。

2.1 候選轉發節點的選擇

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

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

2.2 候選節點的優先級設置

在決定中了候選中繼（CRS）的節點的數量之后，下一個問題是根據優先順序排列這些節點。這個排名為每個傳輸的最大化或最小化提供一個是很重要的客觀標準，如是壽命，延遲和吞吐量。同樣重要的是被選擇的節點的CRS，要提高可靠性的每個傳輸之間的協調。理想情況下，將被用于計算每個候選的優先級度量的屬性必須反映了鏈路，距離，和能量水平等條件。

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

圖1

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

2.3 候選節點的協調

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

3 總結

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

［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］梁紹芳，武穆清，甄巖.適用于多跳無線網絡的機會路由機制[J].計算機工程，2010，19(36)：137-141.