基于移動匯聚節點的組網導航系統路由協議

顧昊倫, 趙國榮, 韓 旭, 高 超

(1.海軍航空大學岸防兵學院, 山東 煙臺 264001; 2.中國人民解放軍第91001部隊, 北京 100854)

0 引 言

無線網絡技術的發展與推廣使得各導航平臺可以借助平臺間的組網與信息協同,在不大幅度增加單個平臺硬件負載的前提下,完成單個平臺難以實現的各類任務[1]。組網導航系統(networked navigation systems, NNSs)正是以導航體傳感器網絡為中心,依托于組網節點間導航信息的協作量測,通過無線交互及信息共享實現網絡內整體導航性能的提升。

實現組網導航的基礎是針對導航體傳感器網絡設計一套高效的組網通信協議。其中,路由協議位于網絡層,是實現NNSs從小尺度網絡與短距傳輸邁向大范圍組網與長距傳輸的關鍵機制。與傳統Ad-hoc網絡相比,NNSs路由協議的設計難點為[2]:① 通信服務類型多種多樣;② 服務質量(quality of service, QoS)傳輸需求;③ 節點能量受限更為明顯;④ 低通信時滯需求。

針對問題①和問題②,文獻[3-5]綜合協作通信和QoS路由,分別以不同目標設計了相應的協作QoS路由協議,實現了差異化服務的策略,提高了帶寬利用率并降低了干擾/串聽等。但文獻[3-5]并未在路由協議的設計中量化QoS指標,且并未建立協作傳輸和多跳傳輸對空間復用率及吞吐量的影響模型等。文獻[6]則針對上述缺點,以三維地理柵格和受控虛擬節點為基礎,將Ebbinghaus記憶原理引入路由搜索的效能優化,設計了一種基于三維地理柵格的衰減記憶協作QoS路由協議(fading memory cooperative QoS routing protocol based on three-dimensional geographic grid,FMCQR),實現了對先驗路由信息的高效利用。但文獻[6]主要解決的仍是問題①和問題②,并未將節點能量受限考慮到設計目標中。因此,盡管其考慮了低通信時滯需求,但當其算法應用至NNSs這種大范圍多節點組網的情形時,網絡能量的迅速衰減使得通信時滯問題反而更加嚴重。

針對問題③和問題④,文獻[7]在低功能耗自適應集簇分層型(low energy adaptive clustering hierarchy,LEACH)協議的基礎上,提出了一種LEACH-DCHS算法,僅從剩余能量多的節點中選取簇頭。但隨著網絡的運行,該種算法將會導致簇頭的數量急劇下降,影響網絡穩定性。文獻[8]考慮文獻[7]中的缺陷,重新構造閾值函數,優先選取剩余能量高的節點為簇頭。但在網絡運行的初始階段,該種算法將會導致簇頭數量爆炸。因此,從控制簇頭數量的變化相對平穩這一角度,文獻[9]和文獻[10]分別提出了集中式LEACH協議和基于窗口滑動和動態節點數目的改進LEACH協議算法控制簇頭期望數目始終在最優范圍內。文獻[7-10]在分簇路由協議的基礎上,從簇頭選取的角度對問題③提出解決方案,優化了網絡的整體運行效率。但均普遍存在簇頭分布過于集中、過于偏向,動態分簇引入額外開銷以及匯聚節點附近的能量空洞等問題。文獻[11]針對上述問題提出了節能非均勻分簇(energy-efficient uneven clustering,EEUC)協議,優化了簇頭分布,緩解了能量空洞問題。但成簇能耗過大,且隨著網絡的運行會導致遠離匯聚節點的簇群能量加速衰減,因此并未從本質上解決能量空洞問題。

針對文獻[7-11]暴露出的問題,文獻[12]證明了具有隨機或受控移動匯聚節點的Ad-hoc網絡負載更加均勻、能耗更低、生命周期更長。文獻[13]提出了一種基于隨機移動匯聚節點的準集中式分簇(quasi centralized clustering approach,QCCA)協議。該協議首先將網絡劃分為不同區域,區域內高能量節點優先成為簇頭,僅當匯聚節點移動至某一區域時由該區域內的簇頭將信息融合發送至匯聚節點。但該種算法極有可能導致某一輪中匯聚節點無法訪問所有區域,通信時滯問題反而加劇。文獻[14]則通過選取代理節點的方式,提出了一種移動基站匯聚(sink mobility support,SMS)協議,但若代理節點死亡,路由重構將會造成較大時滯。文獻[15]綜合中繼跳數,移動匯聚節點的行程長度和節點剩余能量提出了一種能量感知自界跳數算法(energy aware bounded hop count algorithm,EABHCA)協議,該算法具有時滯低的特點,但其能耗和吞吐量方面性能均一般,不適用于NNSs這種大規模網絡。

本文綜合考慮上述文獻中的優缺點,以隨機移動匯聚節點為基礎,將整個網絡區域分為匯聚節點為中心的交叉區域和非交叉區域。交叉區域內的節點為骨干節點,通過構建路由樹將數據傳遞給匯聚節點;非交叉區域內的節點通過鏈式分簇實現數據傳遞并與骨干節點建立聯系。CRTCC路由協議旨在解決以下4個問題:① 通過移動匯聚節點的方式提高網絡內節點的利用率及能量節省率;② 通過建立路由樹的方式提高網絡運行效率,降低通信時滯;③ 通過鏈式分簇的方式進一步降低通信時滯;④ 通過優化鏈式分簇算法降低混合層次鏈式分簇可能帶來的能耗過大的問題。

1 問題描述

1.1 網絡模型

設NNSs共有N個節點及1個匯聚節點。節點主要用于收集、處理和傳遞測距信息和導航信息,具有有限的能量、存儲空間,通信能力一般;匯聚節點主要用于收集并向用戶傳遞節點的導航信息,其能量供應不受限制,存儲空間足夠,通信能力較強。節點獲取測距信息的方式為基于信號到達時間(time of arrival,TOA)法的組網測距[16],解算導航信息包括解算位置信息和姿態信息,分別采取DMDG-3D球面定位算法[17]和四元數UKF姿態估計算法[18]。

設初始時刻之前,網絡內所有節點通過文獻[19]設計的NNSs通信協議均獲取了初始導航信息并建立了網絡空間局部坐標系。設局部坐標系下x軸范圍為[0,X],y軸范圍為[0,Y],z軸范圍為[0,Z]。

基于移動匯聚節點的交叉路由樹構建及鏈式分簇相結合的路由算法(routing algorithm combining cross routing tree construction based on mobile sink and chain clustering, CRTCC)協議采取了“輪”的概念,每一輪包括一個設置階段和一個穩態階段。在設置階段,首先構建一個以移動匯聚節點為中心的交叉區域,區域內的節點為骨干節點,然后根據距離和剩余能量建立路由樹,最后通過鏈式分簇算法將非交叉區域內的節點分為多個簇群。在穩態階段,普通節點將信息傳遞給對應的簇頭,由簇頭將收集到的信息融合處理后傳遞給骨干節點,最后骨干節點通過路由樹將信息傳遞給匯聚節點。與此同時,穩態階段刷新所有節點的導航信息,作為下一輪設置階段的信息基礎。圖1即為某一輪中CRTCC構建的網絡結構示意圖,其中以匯聚節點為中心的正方體向6個邊界面延拓后得到的3個長方體區域的并集即為交叉區域。

圖1 CRTCC構建的網絡結構

1.2 能量模型

與Ad-Hoc網絡類似,NNSs節點在傳輸數據的過程中消耗的能量遠遠大于計算所消耗的能量,因此采取一階無線電模型[20]計算節點消耗的能量。能耗計算公式如下所示：

(1)

式中:ET(k,d)表示某一節點將k-bits數據包發送到d以外另一節點的能耗;ER(k)表示某一節點接受k-bits數據包的能耗;Ee表示某一節點驅動和控制其電子元件的能耗;Ea表示某一節點維持無線電可靠傳輸的能耗。Ea表達式如下所示:

(2)

式中:εf代表自由空間模型下的信號衰減因子;εm代表多徑模型下的信號衰減因子;d0表達式如下所示:

(3)

2 CRTCC路由協議算法

CRTCC路由協議將網絡運行時間分為多輪,在每一輪的設置階段包含5個步驟。

步驟 1匯聚節點路徑規劃及各節點鄰居庫更新。

步驟 2交叉區域構建。

步驟 3交叉區域節點生成路由樹。

步驟 4非交叉區域節點簇頭選取。

步驟 5構建簇結構及路徑選擇。

在隨后的穩態階段,各節點收集的測距信息及導航信息根據設置階段的路由轉發到相應節點進行計算與融合。穩態階段除了完成向匯聚節點發送用戶指定的導航信息外,還需要完成各節點導航信息的刷新,作為下一輪設置階段的信息基礎。

2.1 匯聚節點路徑規劃及各節點鄰居庫更新

算法 1匯聚節點路徑規劃

(4)

圖2 式(4)中各角定義圖

(5)

算法 2鄰居庫更新

由算法1、算法2可知,算法1的時間復雜度為T(1),空間復雜度為O(1);算法2的時間復雜度為T(n2),空間復雜度為O(1)。

2.2 交叉區域構建

記以匯聚節點為中心的正方體邊長為l,0

算法 3交叉區域構建

記φ為交叉區域內節點(骨干節點)坐標的集合。根據點到平面距離公式可得dsBk表達式如下：

(6)

情景 1?k∈{1,2,…,6},dsBk≥0.5l

此情景對應的交叉區域示意圖如圖3所示。

圖3 情景1對應交叉區域

定義U(x,δ)為x的δ領域,U(x,δ)的具體含義為U(x,δ)=[x-δ,x+δ],則根據圖3可知φ的表達式如下所示：

(7)

情景 2?k∈{1,2,…,6},s.t.dsBk<0.5l

此情景共有6種情況,圖4為k=1(即匯聚節點與y=0平面距離小于0.5l)時情景2對應的交叉區域示意圖。

圖4 情景2對應交叉區域(k=1)

k取其余值時可類比推得。因此,k=1,2,…,6時，φ的表達式分別如下所示：

(8)

(9)

(10)

(11)

(12)

(13)

情景 3當匯聚節點與兩個相鄰邊界面的距離同時小于0.5l。不防設這兩個相鄰邊界面為Bk和Bp。

此情景共有12種情況,分別為k=1,p=2;k=1,p=4;k=1,p=5;k=1,p=6;k=2,p=3;k=2,p=5;k=2,p=6;k=3,p=4;k=3,p=5;k=3,p=6;k=4,p=5;k=4,p=6。圖5為k=1,p=2時情景3對應交叉區域示意圖。

圖5 情景3對應交叉區域(k=1,p=2)

當k=1,p=2時:

(14)

當k=1,p=4時:

(15)

當k=1,p=5時:

(16)

當k=1,p=6時:

(17)

當k=2,p=3時:

(18)

當k=2,p=5時:

(19)

當k=2,p=6時:

(20)

當k=3,p=4時:

(21)

當k=3,p=5時:

(22)

當k=3,p=6時:

(23)

當k=4,p=5時:

(24)

當k=4,p=6時:

(25)

情景 4當匯聚節點與3個兩兩相鄰邊界面的距離同時小于0.5l時。不防設這3個兩兩相鄰邊界面為Bk、Bp和Bq。

此情景共有8種情況,分別為k=1,p=2,q=5;k=1,p=2,q=6;k=2,p=3,q=5;k=2,p=3,q=6;k=3,p=4,q=5;k=3,p=4,q=6;k=4,p=1,q=5;k=4,p=1,q=6。圖6為k=4,p=1,q=6時情景4對應交叉區域示意圖。

圖6 時情景4對應交叉區域(k=4,p=1,q=6)

k,p,q取其余值時可類比推得。沿用情景3中的定義,情景4下φ的表達式如下所示。

當k=1,p=2,q=5時:

(26)

當k=1,p=2,q=6時:

(27)

當k=2,p=3,q=5時:

(28)

當k=2,p=3,q=6時:

(29)

當k=3,p=4,q=5時:

(30)

當k=3,p=4,q=6時:

(31)

當k=4,p=1,q=5時:

(32)

當k=4,p=1,q=6時:

(33)

綜上易知算法3的時間復雜度為T(n),空間復雜度為O(1)。

2.3 路由樹生成

算法 4路由樹生成

路由樹的構建過程一共分為5個步驟。

(34)

重復上述所有步驟直至路由樹所有分支構造完畢。上述步驟是以圖3所示交叉區域為例,算法3中生成的其他類型交叉區域均可采用類似算法4的方法得到相應的路由樹。算法4的時間復雜度為T(n),空間復雜度為O(1)。

2.4 簇頭選取

算法 5簇頭選取

CRTCC協議進入成簇階段后,非交叉區域內各節點隨機產生一個0到1之間的數字,隨機數小于閾值τ(η)的節點選為簇頭。

CRTCC協議在LEACH協議的基礎上,在簇頭選取時綜合考慮節點剩余能量以及節點和簇頭之間的位置關系。閾值函數τ(η)表達式如下所示：

(35)

(36)

θ角的引入是為了避免路徑選擇時,多個簇頭與匯聚節點的連線重疊或者夾角很小,導致這些簇頭向匯聚節點派出的螞蟻進行尋優的路徑重合率較高,最終導致重合路徑上的節點能耗過大、快速死亡。設θ角定義為:① 當網絡內沒有簇頭時,θ=0;② 當網絡內僅有一個簇頭時,候選簇頭與匯聚節點的連線同已選簇頭與匯聚節點的連線之間的夾角的倒數為θ;③ 當網絡內存在兩個及兩個以上簇頭時,若候選簇頭與匯聚節點的連線在某兩個已選簇頭與匯聚節點的連線構成的平面內,且在這兩根連線構成的銳角區域范圍內沒有第3根已選簇頭與匯聚節點的連線,則這兩根已選簇頭與匯聚節點連線的角平分線同候選簇頭與匯聚節點連線的夾角為θ。否則取候選簇頭與匯聚節點的連線同所有已選簇頭與匯聚節點的連線夾角的最小值的倒數為θ。

2.5 構建簇結構及路徑選擇

簇頭選取完成后,開始構建簇結構。為增強網絡穩定性,提高魯棒性,簇結構采取混合層次網絡拓撲結構。具體算法如下。

算法 6構建簇結構

步驟 4重復上述步驟1～步驟3,直到所有簇頭全部完成初步的簇結構構建。

步驟 6重復步驟5,直到所有普通節點均能以單跳形式入簇。在此過程中,若有某個普通節點連續ω次尋找到同一個與自身距離最近的簇節點,則令該普通節點直接以單跳方式與此簇節點連接入簇。

步驟 7依次遍歷六條路由樹分支上所有骨干節點(包括匯聚節點)的鄰居庫,將其中屬于非交叉區域的節點找出并令其以單跳方式與自身建立連接。若有同一個非交叉區域內的節點與多個骨干節點建立連接,則選取距離最小的。至此鏈式混合層次簇群結構與路由樹建立連接。

由上述步驟可知,ω可以用來控制成簇收斂速度。由于是混合層次網絡拓撲結構,普通節點之間、簇頭與普通節點之間均可以進行通信,路徑選擇具有多樣性。因此，通過算法7改進蟻群算法給出路徑選擇的依據。

算法 7路徑選擇

(37)

(38)

(39)

(40)

(41)

(42)

由式(40)～式(42)可知,CRTCC協議在信息素更新前,螞蟻先按照自身路徑長度進行排名,路徑短的排在前面,且由于系數加權,排在前面的螞蟻會釋放更多信息素,加快路徑選擇速度。

綜上算法1～算法7構成了CRTCC路由協議。

3 算例仿真

本文應用Matlab平臺,共分4種不同的場景進行仿真,分別記為NNS#1、NNS#2、NNS#3、NNS#4,網絡區域大小為50 m×50 m×50 m、50 m×50 m×50 m、100 m×100 m×100 m、200 m×200 m×200 m.節點數量為50、100、100、150,各節點初始能量均為1 J,Ee=40 nJ/bit,εf=20 pJ/bit/m2,εm=0.002 pJ/bit/m4,導航信息數據包大小為4 096 bit,其余數據包(包括測距包、控制包、廣播包等)大小為196 bit。假設節點剩余能量小于1%時死亡,節點隨機散布在網絡空間。

本文采取文獻[21]中提及的樹型鏈式非均勻分簇路由協議(tree-chain uneven cluster hybrid multi-hop routing algorithm,TUCHM)以及文獻[20]中提及的基于簇樹的節能路由協議(cluster-tree-based energy-efficient routing protowl for wireless sensor network,CTEER)進行比較。文獻[21]提出了一種鏈式分簇結構,但并沒有考慮移動匯聚節點;文獻[20]考慮了移動匯聚節點并提出了路由樹的構建方法,但其分簇僅是最簡單的均勻分簇。

同場景下3種路由協議的節點存活數隨輪數的變化圖如圖7所示。

圖7 4種場景下節點存活數的變化

不同情景下3種路由協議的首個節點死亡輪數(first node death, FND),一半節點存活輪數(half nodes alive, HNA),最后一個節點死亡輪數(last node death, LND),如表1～表3所示。

表1 4種場景下采取THCUM的網絡生命周期指標

表2 4種場景下采取CTEER的網絡生命周期指標

表3 4種場景下采取CRTCC的網絡生命周期指標

根據圖7及表1～表3可知:① THCUM路由協議下的NNSs生命周期短,節點能耗大,死亡速度快,這是因為THCUM路由協議是假設移動匯聚節點固定的,能量空洞問題較其他兩種算法而言比較明顯。② THCUM路由協議下節點數目的增大對其生命周期影響不大,而網絡區域的擴大卻影響很大。這是因為THCUM也是采用鏈式分簇方法,網絡空間內遠離匯聚節點的普通節點或者簇頭增多,鏈路增長,鏈路上節點能耗增大,加速節點的死亡。而由于THCUM采取的是混合層次拓撲結構并設計了尋優路徑算法,節點數目的增多不會導致生命周期的明顯降低。③ CTEER協議由于采用了基于移動匯聚節點的路由樹,其網絡生命周期相對較長,且由于其采取的是均勻分簇,配合路由樹可以取得較好的節能效果。④ CRTCC協議無論是從FND、HNA還是從LND的角度其生命周期都較長,性能高于另外兩種協議。

本文利用每輪傳輸數據包產生的跳數總和來衡量3種路由協議下網絡的通信時滯,并通過前200輪的數據進行仿真分析。不同場景下3種路由協議的每輪跳數總和變化圖如圖8所示。

圖8 4種場景下每輪跳數總和的變化

由圖8可知:① CRTCC協議盡管在生命周期性能方面的表現比較突出,但隨著網絡規模的增大,其通信時滯越來越明顯,在NNS#4情景下超過了TUCHM協議;② TUCHM協議每輪跳數總和并不穩定,這與其混合層次非均勻分簇結構及尋優路徑算法中的啟發因子有關;③ CRTCC協議每輪跳數總和相對比較穩定、通信時滯較低,性能高于另外兩種協議。

4 結 論

本文重點設計了7個算法來構成CRTCC路由協議。以移動匯聚節點為中心的交叉路由樹增加了網絡生命周期,其分支延拓到了網絡的6個臨界面,有效降低了通信時滯的影響;非交叉區域的節點完成鏈式分簇,進一步降低通信時滯;同時改善簇頭選取策略并采用混合層次網絡拓撲結構,優化路徑選擇算法,有效防止了鏈式分簇可能導致的能耗過大、生命周期減小。最后通過與TUCHM協議和CTEER協議在4種場景下的仿真比較,驗證了算法的有效性。