一種基于工業無線網絡的路由和資源分配算法

沈 威，許 娜

(1.中國科學院研究生院，北京 100049；2.北京控制工程研究所，北京 100190)

在無線傳感器網絡中，路由協議負責將數據分組從源節點通過網絡轉發到目的節點。路由的關鍵是要尋找源節點到目的節點間通信延遲較小的路徑，提高整個網絡的利用率，避免通信擁塞并均衡網絡流量。傳感器網絡的路由機制經常與數據融合技術一起應用，通過減少通信量來節省能量。WIA-PA工業無線標準規定[2]：設備在加入網絡后，各個路由設備通過發送信標幀來分配通信資源。信標幀中含有路由設備自身的超幀結構信息。超幀是一種用來組織網絡通信時間分配的邏輯結構。超幀機制要求通信設備之間的時間精確同步，而時間信息的傳播依賴于網絡的路由。路由的實現離不開網絡管理者對通信資源的分配，通信資源的分配效率將直接影響網絡各方面的性能。

1相關研究

1.1無線網絡的路由協議

隨著無線傳感器網絡技術的發展，出現許多專門針對無線傳感器網絡的路由協議。根據應用目標的不同，這些路由協議大致可分為四種類型：能量感知路由協議、基于查詢的路由協議、地理位置路由協議和可靠路由協議。

能量感知路由主要是根據節點的可用能量(剩余能量)或傳輸路徑上的能量需求，選擇數據的轉發路徑。為了均衡消耗整個網絡的能量，SHAH R C.等人提出了一種能量多路徑路由機制[3]。其核心思想是在源節點和目的節點之間建立多條路徑，根據路徑上節點的通信能耗以及節點的剩余能量，給每條路徑設置一個被選擇的概率，將通信能耗分散到多條路徑上，延長網絡的壽命。

定向擴散是一種基于查詢的以數據為中心的路由機制[4]。匯聚節點根據應用需求，廣播興趣消息啟動路由建立過程。中間節點通過興趣表建立從數據源到匯聚節點的數據傳輸梯度，自動形成數據傳輸的多條路徑。在這多條路徑中，使用路徑加強機制生成一條優化的數據傳輸路徑。基于查詢的路由協議還有適用于數據傳輸量較小的傳感器網絡的謠傳路由等。

在某些應用中，節點需要獲取它的位置信息，如森林防火。地理位置路由假設節點已知自己的地理位置信息，以及目的節點或目的區域的地理位置，并依據這些地理信息選擇路由。相關研究包括：GEAR(Geographical and EnergyAwareRouting)機 制[5]、GEM(Graph Embedding)路由[6]和邊界定位地理路由[7]等。還有些應用對數據傳輸的可靠性有較高要求，因此可靠路由協議是路由協議研究的一個重要方向。例如基于不相交路徑的多路徑路由機制，在這種機制中由于各個路徑被設置成不同的優先級，當主路徑失效時，次優路徑將成為新的主路徑。

1.2無線網絡的通信資源分配算法

由于無線通信設備的信道有限，并且信息傳播存在干擾，通信資源的分配效率對網絡的性能影響很大。近年來出現了許多無線通信技術，用于提高無線網絡的通信能力。

碼分多址接入CDMA(Code Division Multiple Access)是在擴頻通信技術上發展起來的一種嶄新而成熟的無線通信技術。CDMA技術的原理是基于擴頻技術，即將需傳送的具有一定信號帶寬信息數據，用一個帶寬遠大于信號帶寬的高速偽隨機碼進行調制，使原數據信號的帶寬被擴展，再經載波調制并發送出去。接收端使用完全相同的偽隨機碼，與接收的帶寬信號作相關處理，把寬帶信號換成原信息數據的窄帶信號即解擴，以實現信息通信。

在前期預實驗的基礎上，以綜合評價、破碎力、揮發性成分和含油量為指標，分別考察不同切片厚度（1、3、5、7 mm）、漂燙溫度（70、80、90、100 ℃）、漂燙時間（1、3、5、7 min）、浸漬液（添加0.1%的食鹽濃度和不添加食鹽）、冷凍時間（1、2、3、4 h）5個預處理單因素對馬鈴薯脆片產品品質的影響。經樣品預處理后進行真空油炸，真空油炸參數為：真空度0.098 MPa、油炸溫度（88±2）℃、時間32 min、離心脫油轉速400 r/min、時間6 min。

時分多址接入TDMA(Time Division Multiple Access)是把一個傳輸通道進行時間分割以傳送若干話路的信息，把N個話路設備接到一條公共的通道上，按一定的次序輪流地給各個設備分配一段使用通道的時間。當輪到某個設備時，這個設備與通道接通，執行操作。與此同時，其他設備與通道的聯系均被切斷。待指定的使用時間間隔一到，則通過時分多路轉換開關把通道連接到下一個要連接的設備上去。

頻分多址接入FDMA(Frequency Division Multiple Access)是數據通信中的一種技術，即不同的用戶分配在時隙相同而頻率不同的信道上。按照這種技術，把在頻分多路傳輸系統中集中控制的頻段根據要求分配給用戶。同固定分配系統相比，頻分多址使通道容量可根據要求動態地進行交換。

2基于工業無線網絡的路由協議

2.1家族譜系描述方法

家族譜系也稱“家譜”，是一種記載一個以血緣關系為主體的家族世系繁衍和重要人物事跡的特殊圖書體裁。世系圖是家譜的一個重要組成部分。家譜在立譜時，便確定了家族世系命名的輩分序列，而且事先標定字號、輩分。本文從網絡拓撲角度出發，借用家譜的術語和結構關系進行網絡結構和路由協議的描述。

圖1所示為典型的樹型結構網絡拓撲。樹型結構是一類重要的非線性數據結構。該結構中，有且僅有一個根(Root)，如A節點。互補相交的有限集均稱為子樹。節點的子樹的根稱為該節點的孩子(Child)，該節點相應地稱為孩子的雙親(Parent)。同一個雙親的孩子之間互稱為兄弟 (Sibling)。沒有孩子的節點的節點也被稱為葉子(Leaf)。這是數據結構中對樹的定義。

圖1 典型的樹型結構網絡拓撲

本文根據家族譜系中的稱謂和關系，將其對應到樹型結構中的節點和節點之間的關系。使得對網絡拓撲和路由協議的描述更加清晰、方便、易于理解。

Root節點稱為根節點，也叫祖先節點。以圖1為例，與根節點直接相連的孩子節點統稱為“第 1代”(B、C、D節點)，“第 1代”的孩子節點統稱為“第 2代”(E、F、H、I、J節點)，以此類推。根節點也稱為“第 0代”。節點的子樹的根稱為該節點“兒子”，相應地，該節點稱為兒子的“父親”。例如：A節點是B節點的父親，B節點是 A節點的兒子。同一個父親的兒子之間互為“親兄弟”，親兄弟有排行順序，稱為“家內排行”。父親節點位于同一代的節點之間互為“堂兄弟”。例如：F節點和H節點互為堂兄弟。堂兄弟有排行順序，稱為“族內排行”。節點與上一代的節點(除了自己的父親節點以外)構成“叔侄”關系。例如：C節點為F節點的叔父，F節點為C節點的子侄。

2.2拓撲結構的建立與路由協議

網絡建立之初，當網絡協調器上電后，根節點廣播發出“子嗣發現”數據包，其中包含發送節點的層變量(level=0)和節點ID。根節點的鄰居節點接收到根節點發出的“子嗣發現”數據包后，將自己的層變量設置為1(level=1)，即確定自己為“第1代”中的一員；同時，“第 1代”需要向父節點發送一個“父子關系確認”數據包(包含節點自身ID)，發送時間根據節點ID適當延遲，以避免碰撞。然后，“第1代”的節點繼續廣播“子嗣發現”數據包。沒有確定層變量的節點在收到“第i代”節點的“子嗣發現”數據包后，記錄發送方的 ID，將自己的層變量設置為(i+1)，并回復“父子關系確認”數據包。這個過程蔓延下去，直到網絡內的所有節點都被賦予一個層變量值，屬于家族樹中的某一代，擁有唯一的父節點和若干子節點。在家族樹的建立過程中，父節點在收到所有子節點發來的確認報文后，需要廣播一個“長幼順序”數據包，其中包含所有子節點的排列順序。子節點收到“長幼順序”數據包后，記錄自己的在兄弟中的排行，也就是“家內排行”。數據包的交互過程如圖2所示。

圖2 數據包的交互過程

由于網絡的樹型結構需要通過數據報文被不斷傳播，本協議還設計了一種具有針對性的樹型結構線性存儲方式。該存儲方式結構清晰，所占空間較小，便于節點設備在本地存儲自己的子樹結構，以及將自己的子樹結構以數據報文的形式發送出去。其數據格式如圖3所示，數據舉例部分依據圖1的網絡結構，根節點的ID為13，其余節點的ID以字母順序編號。當一個子節點接收到其所有子節點發送的“子樹報告”數據包后，它應組織一個包含自己所有子樹的“子樹報告”數據包發送給父節點。

圖3 樹型結構線性存儲報文格式

3基于工業無線網絡的通信資源分配算法

3.1信道與時隙的分配原則

由于無線傳感器網絡的通信特點，不同設備在相互通信時存在干擾。要想同時通信，相鄰層之間不可分配相同的信道。對于信道的分配，可以設置n層作為一個信道重復周期。假設n=3，如圖4所示，Root節點與第1代通信使用ch1信道，第1代與第2代通信使用ch2信道，第2代與第3代通信使用ch3信道，第3代與第4代通信可以重復使用ch1信道，如此循環。

圖4 信道分配實例

由于無線傳感器網絡中的節點一般只裝備一套射頻裝置，所以節點之間進行單播通信時需要分時。

父節點可以向所有子節點發送廣播報文，例如：時間同步報文、數據查詢報文等。如果不同父節點發送的廣播報文覆蓋范圍重合，子節點在接收時就存在干擾，需要分時。如圖4所示，節點1的廣播范圍覆蓋節點4、5，節點2的廣播范圍覆蓋節點6，則節點5和節點 6不能同時接收父節點發送的廣播報文。在家族樹結構中，需要分時通信的情況還包括：父節點相同的節點在與其父節點通信時，需要分時；存在干擾的堂兄弟節點在與其父節點通信時，需要分時。

3.2通信資源的分配算法

網絡可用圖 G=(V，E)來表示，網絡節點數 n=|V|，對e∈E，定義代價函數 Cost(e)：E→R+，時延函數 Delay(e)：E→R+。節點i加入網絡時，先通過父節點從網絡管理者處獲取 ID信息，啟動 Cal_Tree()過程，進行路由選擇和通信資源分配。偽代碼如下：

若同一代的節點發送廣播報文的覆蓋范圍都重合，并且堂兄弟節點在與其父節點通信時均存在干擾，以圖4的拓撲結構為例，資源的分配結果如圖 5(a)所示；若同一代的節點發送廣播報文的覆蓋范圍都重合，而堂兄弟節點在與其父節點通信時均不存在干擾，以圖4的拓撲結構為例，資源的分配結果如圖5(b)所示。

4仿真實驗及分析

仿真實驗在OMNet++平臺上進行，拓撲采用8×8的Mesh結構，64個節點中包含一個網絡管理者，負責全網絡通信資源的分配。實驗節點以中科院自主設計的GAINS-2節點為原型，該節點與Mica2節點兼容。節點的微控制器采用Atmega128L，射頻芯片采用CC1000。網絡協議用Visual C++開發，網絡拓撲由.ned文件生成。

在網絡正常監控階段，當用戶端有查詢任務時，查詢報文將沿著網絡的拓撲結構傳播。圖6為模擬系統隨機生成的網絡拓撲以及路由協議建立的樹型結構。查詢任務一般具有周期性，沿網絡的梯度方向傳播。

網絡維護代價、平均加入時延和平均傳輸時延是衡量路由協議和通信資源分配算法性能的一個重要指標。仿真實驗結果如圖7所示，數據的傳輸時延與鏈路的質量密切相關。

在仿真實驗中，保持監控區域面積不變，改變網絡中節點的數目，為達到應用要求，需要增加節點的射頻距離，則能耗代價與節點的數目密切相關。圖8為網絡能耗代價與節點數目之間的變化關系。

工業無線傳感器監測網絡技術是無線網絡研究領域的一個新的研究方向。本文采用家族譜系的描述方法，提出了一種適用于復雜工業現場監測的工業無線傳感器網絡的路由和通信資源分配算法。這種通信資源分配算法采用分層、分時、分頻相結合的通信策略，充分利用了無線傳感器網絡的特性，能夠有效提高無線網絡的通信效率。由于工業無線監測網絡的工作環境具有多樣性，因此，未來的一個重要任務就是提高路由和通信資源分配算法的適應性和可靠性，克服外界環境變化造成的影響。

[1]孫利民，李建中，陳渝.無線傳感器網絡[M].北京：清華大學出版社，2005.

[2]Industrial communication networks-fieldbus specifications-WIA-PA communication network and communication profile[EB/OL].http：//www.iec.ch，IEC/PAS65C/518/RVD.2010.

[3]SHAH R C， RABAEY J M．Energy aware routing for low energy ad hoc sensor networks[C]．IEEE Wireless Communications and Networking Conference， IEEE， 2002(3)：17-21．

[4]IITANAGONWIWAT C， GOVINDAN R， ESTRIN D.Directed diffusion：A scalable and robustcommunication paradigm for sensor networks[C].The 6th Annual InternationalConference on Mobile Computing and Networks，Boston， MA.2000(5)：113-120.

[5]YU Y，GOVINDAN R，ESTRIN D.Geographical and energy aware routing：A recursive data dissemination protocol for wireless sensor networks[R].UCLA Computer Science DepartmentTechnicalReportUCLA/CSD-TR-01-0023.2001(5)：1132-1145.

[6]KARP B， KUNG H T.GPSR：Greedy perimeter stateless routing for wireless networks[C].The 6th Annual InternationalConference on Mobile Computing and Networks，Boston， MA.2000(5)：6-11.

[7]RAO A， RATNASAMY S， PAPADIMITRIOU C.Geographic routing without location information[C].The 9th Annual InternationalConferenceon MobileComputingand Networks， San Diego， CA.2003(9)：96-108．