《電子技術(shù)應(yīng)用》
您所在的位置:首頁 > 通信與網(wǎng)絡(luò) > 設(shè)計(jì)應(yīng)用 > 一種基于工業(yè)無線網(wǎng)絡(luò)的路由和資源分配算法
一種基于工業(yè)無線網(wǎng)絡(luò)的路由和資源分配算法
來源:微型機(jī)與應(yīng)用2010年第15期
沈 威1,許 娜2
(1.中國科學(xué)院研究生院,北京 100049;2.北京控制工程研究所,北京 100190)
摘要: 采用家族譜系的描述方法,提出了一種適用于復(fù)雜現(xiàn)場監(jiān)測的工業(yè)無線傳感器網(wǎng)絡(luò)路由和通信資源分配算法。該算法利用無線傳感器網(wǎng)絡(luò)的廣播特性,采用分層、分時(shí)和分頻相結(jié)合的策略實(shí)現(xiàn)路由和通信資源的分配,具有條理清晰、實(shí)現(xiàn)簡單的特點(diǎn)。仿真測試表明,該算法能夠有效提高無線網(wǎng)絡(luò)的通信效率,可靠性高,并具有良好的可擴(kuò)展性。
Abstract:
Key words :

摘  要: 采用家族譜系的描述方法,提出了一種適用于復(fù)雜現(xiàn)場監(jiān)測的工業(yè)無線傳感器網(wǎng)絡(luò)路由和通信資源分配算法。該算法利用無線傳感器網(wǎng)絡(luò)的廣播特性,采用分層、分時(shí)和分頻相結(jié)合的策略實(shí)現(xiàn)路由和通信資源的分配,具有條理清晰、實(shí)現(xiàn)簡單的特點(diǎn)。仿真測試表明,該算法能夠有效提高無線網(wǎng)絡(luò)的通信效率,可靠性高,并具有良好的可擴(kuò)展性。
關(guān)鍵詞: 工業(yè)現(xiàn)場;無線網(wǎng)絡(luò);路由;資源分配

    隨著半導(dǎo)體、微電子、通信和計(jì)算機(jī)技術(shù)的飛速發(fā)展,無線傳感器網(wǎng)絡(luò)技術(shù)取得了巨大的進(jìn)步。由于無線傳感器網(wǎng)絡(luò)能夠獲取多種客觀物理信息,已被應(yīng)用在軍事國防、工農(nóng)業(yè)控制、城市管理、生物醫(yī)療、環(huán)境監(jiān)測、搶險(xiǎn)救災(zāi)等諸多領(lǐng)域。尤其是在惡劣環(huán)境下的工業(yè)現(xiàn)場設(shè)備監(jiān)測(如大型工廠的冶金設(shè)備監(jiān)測、綿延數(shù)千公里的輸油管道監(jiān)測和巨型船舶測試場的監(jiān)測等)是近年來的研究熱點(diǎn)[1]。
    在無線傳感器網(wǎng)絡(luò)中,路由協(xié)議負(fù)責(zé)將數(shù)據(jù)分組從源節(jié)點(diǎn)通過網(wǎng)絡(luò)轉(zhuǎn)發(fā)到目的節(jié)點(diǎn)。路由的關(guān)鍵是要尋找源節(jié)點(diǎn)到目的節(jié)點(diǎn)間通信延遲較小的路徑,提高整個(gè)網(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ò)后,各個(gè)路由設(shè)備通過發(fā)送信標(biāo)幀來分配通信資源。信標(biāo)幀中含有路由設(shè)備自身的超幀結(jié)構(gòu)信息。超幀是一種用來組織網(wǎng)絡(luò)通信時(shí)間分配的邏輯結(jié)構(gòu)。超幀機(jī)制要求通信設(shè)備之間的時(shí)間精確同步,而時(shí)間信息的傳播依賴于網(wǎng)絡(luò)的路由。路由的實(shí)現(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é)點(diǎn)的可用能量(剩余能量)或傳輸路徑上的能量需求,選擇數(shù)據(jù)的轉(zhuǎn)發(fā)路徑。為了均衡消耗整個(gè)網(wǎng)絡(luò)的能量,SHAH R C.等人提出了一種能量多路徑路由機(jī)制[3]。其核心思想是在源節(jié)點(diǎn)和目的節(jié)點(diǎn)之間建立多條路徑,根據(jù)路徑上節(jié)點(diǎn)的通信能耗以及節(jié)點(diǎn)的剩余能量,給每條路徑設(shè)置一個(gè)被選擇的概率,將通信能耗分散到多條路徑上,延長網(wǎng)絡(luò)的壽命。
    定向擴(kuò)散是一種基于查詢的以數(shù)據(jù)為中心的路由機(jī)制[4]。匯聚節(jié)點(diǎn)根據(jù)應(yīng)用需求,廣播興趣消息啟動(dòng)路由建立過程。中間節(jié)點(diǎn)通過興趣表建立從數(shù)據(jù)源到匯聚節(jié)點(diǎn)的數(shù)據(jù)傳輸梯度,自動(dòng)形成數(shù)據(jù)傳輸?shù)亩鄺l路徑。在這多條路徑中,使用路徑加強(qiáng)機(jī)制生成一條優(yōu)化的數(shù)據(jù)傳輸路徑?;诓樵兊穆酚蓞f(xié)議還有適用于數(shù)據(jù)傳輸量較小的傳感器網(wǎng)絡(luò)的謠傳路由等。
    在某些應(yīng)用中,節(jié)點(diǎn)需要獲取它的位置信息,如森林防火。地理位置路由假設(shè)節(jié)點(diǎn)已知自己的地理位置信息,以及目的節(jié)點(diǎn)或目的區(qū)域的地理位置,并依據(jù)這些地理信息選擇路由。相關(guān)研究包括:GEAR(Geographical and Energy Aware Routing)機(jī)制[5]、GEM(Graph Embedding)路由[6]和邊界定位地理路由[7]等。還有些應(yīng)用對數(shù)據(jù)傳輸?shù)目煽啃杂休^高要求,因此可靠路由協(xié)議是路由協(xié)議研究的一個(gè)重要方向。例如基于不相交路徑的多路徑路由機(jī)制,在這種機(jī)制中由于各個(gè)路徑被設(shè)置成不同的優(yōu)先級,當(dāng)主路徑失效時(shí),次優(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ù),用一個(gè)帶寬遠(yuǎn)大于信號帶寬的高速偽隨機(jī)碼進(jìn)行調(diào)制,使原數(shù)據(jù)信號的帶寬被擴(kuò)展,再經(jīng)載波調(diào)制并發(fā)送出去。接收端使用完全相同的偽隨機(jī)碼,與接收的帶寬信號作相關(guān)處理,把寬帶信號換成原信息數(shù)據(jù)的窄帶信號即解擴(kuò),以實(shí)現(xiàn)信息通信。
    時(shí)分多址接入TDMA(Time Division Multiple Access)是把一個(gè)傳輸通道進(jìn)行時(shí)間分割以傳送若干話路的信息,把N個(gè)話路設(shè)備接到一條公共的通道上,按一定的次序輪流地給各個(gè)設(shè)備分配一段使用通道的時(shí)間。當(dāng)輪到某個(gè)設(shè)備時(shí),這個(gè)設(shè)備與通道接通,執(zhí)行操作。與此同時(shí),其他設(shè)備與通道的聯(lián)系均被切斷。待指定的使用時(shí)間間隔一到,則通過時(shí)分多路轉(zhuǎn)換開關(guān)把通道連接到下一個(gè)要連接的設(shè)備上去。
    頻分多址接入FDMA(Frequency Division Multiple Access)是數(shù)據(jù)通信中的一種技術(shù),即不同的用戶分配在時(shí)隙相同而頻率不同的信道上。按照這種技術(shù),把在頻分多路傳輸系統(tǒng)中集中控制的頻段根據(jù)要求分配給用戶。同固定分配系統(tǒng)相比,頻分多址使通道容量可根據(jù)要求動(dòng)態(tài)地進(jìn)行交換。
2 基于工業(yè)無線網(wǎng)絡(luò)的路由協(xié)議
2.1 家族譜系描述方法

    家族譜系也稱“家譜”,是一種記載一個(gè)以血緣關(guān)系為主體的家族世系繁衍和重要人物事跡的特殊圖書體裁。世系圖是家譜的一個(gè)重要組成部分。家譜在立譜時(shí),便確定了家族世系命名的輩分序列,而且事先標(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)中,有且僅有一個(gè)根(Root),如A節(jié)點(diǎn)?;パa(bǔ)相交的有限集均稱為子樹。節(jié)點(diǎn)的子樹的根稱為該節(jié)點(diǎn)的孩子(Child),該節(jié)點(diǎn)相應(yīng)地稱為孩子的雙親(Parent)。同一個(gè)雙親的孩子之間互稱為兄弟(Sibling)。沒有孩子的節(jié)點(diǎn)的節(jié)點(diǎn)也被稱為葉子(Leaf)。這是數(shù)據(jù)結(jié)構(gòu)中對樹的定義。

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

    由于網(wǎng)絡(luò)的樹型結(jié)構(gòu)需要通過數(shù)據(jù)報(bào)文被不斷傳播,本協(xié)議還設(shè)計(jì)了一種具有針對性的樹型結(jié)構(gòu)線性存儲方式。該存儲方式結(jié)構(gòu)清晰,所占空間較小,便于節(jié)點(diǎn)設(shè)備在本地存儲自己的子樹結(jié)構(gòu),以及將自己的子樹結(jié)構(gòu)以數(shù)據(jù)報(bào)文的形式發(fā)送出去。其數(shù)據(jù)格式如圖3所示,數(shù)據(jù)舉例部分依據(jù)圖1的網(wǎng)絡(luò)結(jié)構(gòu),根節(jié)點(diǎn)的ID為13,其余節(jié)點(diǎn)的ID以字母順序編號。當(dāng)一個(gè)子節(jié)點(diǎn)接收到其所有子節(jié)點(diǎn)發(fā)送的“子樹報(bào)告”數(shù)據(jù)包后,它應(yīng)組織一個(gè)包含自己所有子樹的“子樹報(bào)告”數(shù)據(jù)包發(fā)送給父節(jié)點(diǎn)。


3 基于工業(yè)無線網(wǎng)絡(luò)的通信資源分配算法
3.1 信道與時(shí)隙的分配原則

    由于無線傳感器網(wǎng)絡(luò)的通信特點(diǎn),不同設(shè)備在相互通信時(shí)存在干擾。要想同時(shí)通信,相鄰層之間不可分配相同的信道。對于信道的分配,可以設(shè)置n層作為一個(gè)信道重復(fù)周期。假設(shè)n=3,如圖4所示,Root節(jié)點(diǎn)與第1代通信使用ch1信道,第1代與第2代通信使用ch2信道,第2代與第3代通信使用ch3信道,第3代與第4代通信可以重復(fù)使用ch1信道,如此循環(huán)。
    由于無線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)一般只裝備一套射頻裝置,所以節(jié)點(diǎn)之間進(jìn)行單播通信時(shí)需要分時(shí)。
    父節(jié)點(diǎn)可以向所有子節(jié)點(diǎn)發(fā)送廣播報(bào)文,例如:時(shí)間同步報(bào)文、數(shù)據(jù)查詢報(bào)文等。如果不同父節(jié)點(diǎn)發(fā)送的廣播報(bào)文覆蓋范圍重合,子節(jié)點(diǎn)在接收時(shí)就存在干擾,需要分時(shí)。如圖4所示,節(jié)點(diǎn)1的廣播范圍覆蓋節(jié)點(diǎn)4、5,節(jié)點(diǎn)2的廣播范圍覆蓋節(jié)點(diǎn)6,則節(jié)點(diǎn)5和節(jié)點(diǎn)6不能同時(shí)接收父節(jié)點(diǎn)發(fā)送的廣播報(bào)文。在家族樹結(jié)構(gòu)中,需要分時(shí)通信的情況還包括:父節(jié)點(diǎn)相同的節(jié)點(diǎn)在與其父節(jié)點(diǎn)通信時(shí),需要分時(shí);存在干擾的堂兄弟節(jié)點(diǎn)在與其父節(jié)點(diǎn)通信時(shí),需要分時(shí)。

3.2 通信資源的分配算法
  
    若同一代的節(jié)點(diǎn)發(fā)送廣播報(bào)文的覆蓋范圍都重合,并且堂兄弟節(jié)點(diǎn)在與其父節(jié)點(diǎn)通信時(shí)均存在干擾,以圖4的拓?fù)浣Y(jié)構(gòu)為例,資源的分配結(jié)果如圖5(a)所示;若同一代的節(jié)點(diǎn)發(fā)送廣播報(bào)文的覆蓋范圍都重合,而堂兄弟節(jié)點(diǎn)在與其父節(jié)點(diǎn)通信時(shí)均不存在干擾,以圖4的拓?fù)浣Y(jié)構(gòu)為例,資源的分配結(jié)果如圖5(b)所示。

4 仿真實(shí)驗(yàn)及分析
    仿真實(shí)驗(yàn)在OMNet++平臺上進(jìn)行,拓?fù)洳捎?×8的Mesh結(jié)構(gòu),64個(gè)節(jié)點(diǎn)中包含一個(gè)網(wǎng)絡(luò)管理者,負(fù)責(zé)全網(wǎng)絡(luò)通信資源的分配。實(shí)驗(yàn)節(jié)點(diǎn)以中科院自主設(shè)計(jì)的GAINS-2節(jié)點(diǎn)為原型,該節(jié)點(diǎn)與Mica2節(jié)點(diǎn)兼容。節(jié)點(diǎn)的微控制器采用Atmega128L,射頻芯片采用CC1000。網(wǎng)絡(luò)協(xié)議用Visual C++開發(fā),網(wǎng)絡(luò)拓?fù)溆?ned文件生成。
    在網(wǎng)絡(luò)正常監(jiān)控階段,當(dāng)用戶端有查詢?nèi)蝿?wù)時(shí),查詢報(bào)文將沿著網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)傳播。圖6為模擬系統(tǒng)隨機(jī)生成的網(wǎng)絡(luò)拓?fù)湟约奥酚蓞f(xié)議建立的樹型結(jié)構(gòu)。查詢?nèi)蝿?wù)一般具有周期性,沿網(wǎng)絡(luò)的梯度方向傳播。

    網(wǎng)絡(luò)維護(hù)代價(jià)、平均加入時(shí)延和平均傳輸時(shí)延是衡量路由協(xié)議和通信資源分配算法性能的一個(gè)重要指標(biāo)。仿真實(shí)驗(yàn)結(jié)果如圖7所示,數(shù)據(jù)的傳輸時(shí)延與鏈路的質(zhì)量密切相關(guān)。
    在仿真實(shí)驗(yàn)中,保持監(jiān)控區(qū)域面積不變,改變網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目,為達(dá)到應(yīng)用要求,需要增加節(jié)點(diǎn)的射頻距離,則能耗代價(jià)與節(jié)點(diǎn)的數(shù)目密切相關(guān)。圖8為網(wǎng)絡(luò)能耗代價(jià)與節(jié)點(diǎn)數(shù)目之間的變化關(guān)系。

    工業(yè)無線傳感器監(jiān)測網(wǎng)絡(luò)技術(shù)是無線網(wǎng)絡(luò)研究領(lǐng)域的一個(gè)新的研究方向。本文采用家族譜系的描述方法,提出了一種適用于復(fù)雜工業(yè)現(xiàn)場監(jiān)測的工業(yè)無線傳感器網(wǎng)絡(luò)的路由和通信資源分配算法。這種通信資源分配算法采用分層、分時(shí)、分頻相結(jié)合的通信策略,充分利用了無線傳感器網(wǎng)絡(luò)的特性,能夠有效提高無線網(wǎng)絡(luò)的通信效率。由于工業(yè)無線監(jiān)測網(wǎng)絡(luò)的工作環(huán)境具有多樣性,因此,未來的一個(gè)重要任務(wù)就是提高路由和通信資源分配算法的適應(yīng)性和可靠性,克服外界環(huán)境變化造成的影響。
參考文獻(xiàn)
[1] 孫利民,李建中,陳渝.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社,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 robust communication paradigm for sensor networks[C]. The 6th Annual International Conference 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 Department Technical Report UCLA/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 International Conference 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 International Conference on Mobile Computing and Networks, San Diego, CA. 2003(9):96-108.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載。