一種基于工業(yè)無(wú)線(xiàn)網(wǎng)絡(luò )的路由和資源分配算法

隨著(zhù)半導體、微電子、通信和計算機技術(shù)的飛速發(fā)展，無(wú)線(xiàn)傳感器網(wǎng)絡(luò )技術(shù)取得了巨大的進(jìn)步。由于無(wú)線(xiàn)傳感器網(wǎng)絡(luò )能夠獲取多種客觀(guān)物理信息，已被應用在軍事國防、工農業(yè)控制、城市管理、生物醫療、環(huán)境監測、搶險救災等諸多領(lǐng)域。尤其是在惡劣環(huán)境下的工業(yè)現場(chǎng)設備監測(如大型工廠(chǎng)的冶金設備監測、綿延數千公里的輸油管道監測和巨型船舶測試場(chǎng)的監測等)是近年來(lái)的研究熱點(diǎn)[1]。
在無(wú)線(xiàn)傳感器網(wǎng)絡(luò )中，路由協(xié)議負責將數據分組從源節點(diǎn)通過(guò)網(wǎng)絡(luò )轉發(fā)到目的節點(diǎn)。路由的關(guān)鍵是要尋找源節點(diǎn)到目的節點(diǎn)間通信延遲較小的路徑，提高整個(gè)網(wǎng)絡(luò )的利用率，避免通信擁塞并均衡網(wǎng)絡(luò )流量。傳感器網(wǎng)絡(luò )的路由機制經(jīng)常與數據融合技術(shù)一起應用，通過(guò)減少通信量來(lái)節省能量。WIA-PA工業(yè)無(wú)線(xiàn)標準規定[2]：設備在加入網(wǎng)絡(luò )后，各個(gè)路由設備通過(guò)發(fā)送信標幀來(lái)分配通信資源。信標幀中含有路由設備自身的超幀結構信息。超幀是一種用來(lái)組織網(wǎng)絡(luò )通信時(shí)間分配的邏輯結構。超幀機制要求通信設備之間的時(shí)間精確同步，而時(shí)間信息的傳播依賴(lài)于網(wǎng)絡(luò )的路由。路由的實(shí)現離不開(kāi)網(wǎng)絡(luò )管理者對通信資源的分配，通信資源的分配效率將直接影響網(wǎng)絡(luò )各方面的性能。
1 相關(guān)研究
1.1 無(wú)線(xiàn)網(wǎng)絡(luò )的路由協(xié)議
隨著(zhù)無(wú)線(xiàn)傳感器網(wǎng)絡(luò )技術(shù)的發(fā)展，出現許多專(zhuān)門(mén)針對無(wú)線(xiàn)傳感器網(wǎng)絡(luò )的路由協(xié)議。根據應用目標的不同，這些路由協(xié)議大致可分為四種類(lèi)型：能量感知路由協(xié)議、基于查詢(xún)的路由協(xié)議、地理位置路由協(xié)議和可靠路由協(xié)議。
能量感知路由主要是根據節點(diǎn)的可用能量(剩余能量)或傳輸路徑上的能量需求，選擇數據的轉發(fā)路徑。為了均衡消耗整個(gè)網(wǎng)絡(luò )的能量，SHAH R C.等人提出了一種能量多路徑路由機制[3]。其核心思想是在源節點(diǎn)和目的節點(diǎn)之間建立多條路徑，根據路徑上節點(diǎn)的通信能耗以及節點(diǎn)的剩余能量，給每條路徑設置一個(gè)被選擇的概率，將通信能耗分散到多條路徑上，延長(cháng)網(wǎng)絡(luò )的壽命。
定向擴散是一種基于查詢(xún)的以數據為中心的路由機制[4]。匯聚節點(diǎn)根據應用需求，廣播興趣消息啟動(dòng)路由建立過(guò)程。中間節點(diǎn)通過(guò)興趣表建立從數據源到匯聚節點(diǎn)的數據傳輸梯度，自動(dòng)形成數據傳輸的多條路徑。在這多條路徑中，使用路徑加強機制生成一條優(yōu)化的數據傳輸路徑。基于查詢(xún)的路由協(xié)議還有適用于數據傳輸量較小的傳感器網(wǎng)絡(luò )的謠傳路由等。
在某些應用中，節點(diǎn)需要獲取它的位置信息，如森林防火。地理位置路由假設節點(diǎn)已知自己的地理位置信息，以及目的節點(diǎn)或目的區域的地理位置，并依據這些地理信息選擇路由。相關(guān)研究包括：GEAR(Geographical and Energy Aware Routing)機制[5]、GEM(Graph Embedding)路由[6]和邊界定位地理路由[7]等。還有些應用對數據傳輸的可靠性有較高要求，因此可靠路由協(xié)議是路由協(xié)議研究的一個(gè)重要方向。例如基于不相交路徑的多路徑路由機制，在這種機制中由于各個(gè)路徑被設置成不同的優(yōu)先級，當主路徑失效時(shí)，次優(yōu)路徑將成為新的主路徑。
1.2 無(wú)線(xiàn)網(wǎng)絡(luò )的通信資源分配算法
由于無(wú)線(xiàn)通信設備的信道有限，并且信息傳播存在干擾，通信資源的分配效率對網(wǎng)絡(luò )的性能影響很大。近年來(lái)出現了許多無(wú)線(xiàn)通信技術(shù)，用于提高無(wú)線(xiàn)網(wǎng)絡(luò )的通信能力。
碼分多址接入CDMA(Code Division Multiple Access)是在擴頻通信技術(shù)上發(fā)展起來(lái)的一種嶄新而成熟的無(wú)線(xiàn)通信技術(shù)。CDMA技術(shù)的原理是基于擴頻技術(shù)，即將需傳送的具有一定信號帶寬信息數據，用一個(gè)帶寬遠大于信號帶寬的高速偽隨機碼進(jìn)行調制，使原數據信號的帶寬被擴展，再經(jīng)載波調制并發(fā)送出去。接收端使用完全相同的偽隨機碼，與接收的帶寬信號作相關(guān)處理，把寬帶信號換成原信息數據的窄帶信號即解擴，以實(shí)現信息通信。
時(shí)分多址接入TDMA(Time Division Multiple Access)是把一個(gè)傳輸通道進(jìn)行時(shí)間分割以傳送若干話(huà)路的信息，把N個(gè)話(huà)路設備接到一條公共的通道上，按一定的次序輪流地給各個(gè)設備分配一段使用通道的時(shí)間。當輪到某個(gè)設備時(shí)，這個(gè)設備與通道接通，執行操作。與此同時(shí)，其他設備與通道的聯(lián)系均被切斷。待指定的使用時(shí)間間隔一到，則通過(guò)時(shí)分多路轉換開(kāi)關(guān)把通道連接到下一個(gè)要連接的設備上去。
頻分多址接入FDMA(Frequency Division Multiple Access)是數據通信中的一種技術(shù)，即不同的用戶(hù)分配在時(shí)隙相同而頻率不同的信道上。按照這種技術(shù)，把在頻分多路傳輸系統中集中控制的頻段根據要求分配給用戶(hù)。同固定分配系統相比，頻分多址使通道容量可根據要求動(dòng)態(tài)地進(jìn)行交換。
2 基于工業(yè)無(wú)線(xiàn)網(wǎng)絡(luò )的路由協(xié)議
2.1 家族譜系描述方法
家族譜系也稱(chēng)“家譜”，是一種記載一個(gè)以血緣關(guān)系為主體的家族世系繁衍和重要人物事跡的特殊圖書(shū)體裁。世系圖是家譜的一個(gè)重要組成部分。家譜在立譜時(shí)，便確定了家族世系命名的輩分序列，而且事先標定字號、輩分。本文從網(wǎng)絡(luò )拓撲角度出發(fā)，借用家譜的術(shù)語(yǔ)和結構關(guān)系進(jìn)行網(wǎng)絡(luò )結構和路由協(xié)議的描述。
圖1所示為典型的樹(shù)型結構網(wǎng)絡(luò )拓撲。樹(shù)型結構是一類(lèi)重要的非線(xiàn)性數據結構。該結構中，有且僅有一個(gè)根(Root)，如A節點(diǎn)?；パa相交的有限集均稱(chēng)為子樹(shù)。節點(diǎn)的子樹(shù)的根稱(chēng)為該節點(diǎn)的孩子(Child)，該節點(diǎn)相應地稱(chēng)為孩子的雙親(Parent)。同一個(gè)雙親的孩子之間互稱(chēng)為兄弟(Sibling)。沒(méi)有孩子的節點(diǎn)的節點(diǎn)也被稱(chēng)為葉子(Leaf)。這是數據結構中對樹(shù)的定義。

本文根據家族譜系中的稱(chēng)謂和關(guān)系，將其對應到樹(shù)型結構中的節點(diǎn)和節點(diǎn)之間的關(guān)系。使得對網(wǎng)絡(luò )拓撲和路由協(xié)議的描述更加清晰、方便、易于理解。
Root節點(diǎn)稱(chēng)為根節點(diǎn)，也叫祖先節點(diǎn)。以圖1為例，與根節點(diǎn)直接相連的孩子節點(diǎn)統稱(chēng)為“第1代”(B、C、D節點(diǎn))，“第1代”的孩子節點(diǎn)統稱(chēng)為“第2代”(E、F、H、I、J節點(diǎn))，以此類(lèi)推。根節點(diǎn)也稱(chēng)為“第0代”。節點(diǎn)的子樹(shù)的根稱(chēng)為該節點(diǎn)“兒子”，相應地，該節點(diǎn)稱(chēng)為兒子的“父親”。例如：A節點(diǎn)是B節點(diǎn)的父親，B節點(diǎn)是A節點(diǎn)的兒子。同一個(gè)父親的兒子之間互為“親兄弟”，親兄弟有排行順序，稱(chēng)為“家內排行”。父親節點(diǎn)位于同一代的節點(diǎn)之間互為“堂兄弟”。例如：F節點(diǎn)和H節點(diǎn)互為堂兄弟。堂兄弟有排行順序，稱(chēng)為“族內排行”。節點(diǎn)與上一代的節點(diǎn)(除了自己的父親節點(diǎn)以外)構成“叔侄”關(guān)系。例如：C節點(diǎn)為F節點(diǎn)的叔父，F節點(diǎn)為C節點(diǎn)的子侄。
2.2 拓撲結構的建立與路由協(xié)議
網(wǎng)絡(luò )建立之初，當網(wǎng)絡(luò )協(xié)調器上電后，根節點(diǎn)廣播發(fā)出“子嗣發(fā)現”數據包，其中包含發(fā)送節點(diǎn)的層變量(level=0)和節點(diǎn)ID。根節點(diǎn)的鄰居節點(diǎn)接收到根節點(diǎn)發(fā)出的“子嗣發(fā)現”數據包后，將自己的層變量設置為1(level=1)，即確定自己為“第1代”中的一員；同時(shí)，“第1代”需要向父節點(diǎn)發(fā)送一個(gè)“父子關(guān)系確認”數據包(包含節點(diǎn)自身ID)，發(fā)送時(shí)間根據節點(diǎn)ID適當延遲，以避免碰撞。然后，“第1代”的節點(diǎn)繼續廣播“子嗣發(fā)現”數據包。沒(méi)有確定層變量的節點(diǎn)在收到“第i代”節點(diǎn)的“子嗣發(fā)現”數據包后，記錄發(fā)送方的ID，將自己的層變量設置為(i+1)，并回復“父子關(guān)系確認”數據包。這個(gè)過(guò)程蔓延下去，直到網(wǎng)絡(luò )內的所有節點(diǎn)都被賦予一個(gè)層變量值，屬于家族樹(shù)中的某一代，擁有唯一的父節點(diǎn)和若干子節點(diǎn)。在家族樹(shù)的建立過(guò)程中，父節點(diǎn)在收到所有子節點(diǎn)發(fā)來(lái)的確認報文后，需要廣播一個(gè)“長(cháng)幼順序”數據包，其中包含所有子節點(diǎn)的排列順序。子節點(diǎn)收到“長(cháng)幼順序”數據包后，記錄自己的在兄弟中的排行，也就是“家內排行”。數據包的交互過(guò)程如圖2所示。