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

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

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