一種自適應的混合型無線傳感器網(wǎng)絡拓撲控制算法

1、第 23卷 第 3期 2010年 3月傳 感 技 術 學 報CH I N ESE JOURNAL OF SE N S ORS AND ACT UATORSVo. l 23 No . 3M ar . 2010項目來源 :國家自然科學基金項目資助 (60673132; 廣東省 重大科技 專項項 目資助 (2009A 080207008; 廣東 省自然 科學基 金21 :An Adaptive Hybri d Topology Control forW SN*LI Shaochun , CH ENG L i ang l un*(Net w orks&Syste m R ese a rch I

2、nstitute , Fa c u lt y of Au t oma ti on, Guangd ong Universit y of T ec hnology , G uangzhou 510006, Ch ina Abst ract :H ybri d topology con tro l algorithm for spec ific app lications is one o f the hot issues in the field ofW SN to pology contro. l On the basis of the study o f c l a ssica l orie

3、nted event driven net w ork topo l o gy control a l g orit h m ASCENT, an adapti v e hybri d topo logy contro l algorithm AH TC is proposed . The proble m s o fASCNET are solved when app l y ing to net w ork scenes o f large sca le driven even. t The proble m s such as fa ilure adaption i n large sc

4、a le net w ork , node resi d ual ener gy and h i g h rate o f net w or k packet l o ss are less consi d esed . S i m ulati o n resu lts show that t h e i m proved algor ith m has better energy e fficiency and stability . K ey w ords :W S N; topo logy contro; l adaptive hybrid ; ASCE NT; AHTC EEACC :

5、6150P一種自適應的混合型無線傳感器網(wǎng)絡拓撲控制算法*李少春 , 程良倫*(廣東工業(yè)大學自動化學院 控制網(wǎng) 絡與系統(tǒng)研究所 , 廣州 510006摘 要 :針對特定應用場合的混合型拓撲控制算法是 W SN 拓撲控 制領域 的研究熱 點之一。 在研究 經(jīng)典的面 向事件 驅動型網(wǎng)絡拓撲控制算法 A SCENT 基礎上 , 提出了一種自適應的混合型拓 撲控制算法 AHTC 算法。針對大 規(guī)模事件驅 動型網(wǎng)絡 場景應用 , 解決了 A SC N ET 算法不能適應于大規(guī)模網(wǎng)絡、 未考慮節(jié)點剩余能量、 網(wǎng)絡 丟包率高等 問題。仿真結 果表明 , 改進的 算法有更好的節(jié)能性 和穩(wěn)定性。關鍵詞 :無線傳感

6、器網(wǎng)絡 ; 拓撲控制 ; 自適應 ; 混合型 ; A SCENT; AHTC 中圖分類號 :TP393 文獻標識碼 :A 文章編號 :1004-1699(2010 03-0428-06 無線傳感器網(wǎng)絡的首要設計目標之一是降低全 網(wǎng)能耗。而拓撲控制是實現(xiàn)這一目標的重要支撐基 礎。拓撲控制從研究方向上分可以分為 :節(jié)點功率 控制、 層次型拓撲控制、 網(wǎng)內節(jié)點協(xié)同啟發(fā)機制 1。 節(jié)點功率控制機制調節(jié)網(wǎng)絡中每個 節(jié)點的發(fā)射功 率 , 目的是在保證全網(wǎng)連通性的情況下 , 均衡節(jié)點一 跳 距 離 的 鄰 居 數(shù) 目。 經(jīng) 典 算 法 有 :LMA2、DRNG 3、 L M ST 4等 ; 層次型拓 撲控制

7、是 選擇網(wǎng)絡 中的一些節(jié)點成為骨干節(jié)點 , 構架起包轉發(fā)的骨干 網(wǎng)絡 , 其他非骨干網(wǎng)節(jié)點接受骨干節(jié)點管轄。經(jīng)典 算法有 :GAF 5、 LEACH 6、GB R 7等 ; 網(wǎng)內節(jié)點協(xié)同 啟發(fā)機制是節(jié)點按照周邊通訊環(huán)境的變化 , 進行自 主控制以及和鄰居節(jié)點進行交互的機制。無線傳感器是一種面向實際應用的多樣性網(wǎng)絡。在隨機部署 的大規(guī)模密集型網(wǎng)絡中 , 經(jīng)典的拓撲控制機制無法 適應其特殊要求。尤其是對于大規(guī)模事件驅動型網(wǎng) 絡。功率控制由于缺乏休眠機制而無法適應大規(guī)模 密集型網(wǎng)絡。層次型拓撲可以近似的用于大規(guī)模網(wǎng) 絡但是缺乏本地功率優(yōu)化和自適應性。而協(xié)同啟發(fā) 機制的缺點在于局部的自適應性而不能很好

8、的擴展 到大規(guī)模網(wǎng)絡。且大多數(shù)算法都沒有考慮節(jié)點剩余 能量和負載均衡問題。本文試圖通過結合各種拓撲控制機制的優(yōu)勢來 構建一 種 適應 于大 規(guī) 模事 件 驅動 型 網(wǎng) 絡場 景 的 W SN 拓撲控制算法。在這種場合下 , 興趣事件的低 概率發(fā)生前提使得網(wǎng)絡中傳遞的數(shù)據(jù)量較小 , 因此第 3期 李少春 , 程良倫等 :一種自適應的混合型無線傳感器網(wǎng)絡拓撲控制算法大部分能耗會流失在節(jié)點偵聽環(huán)節(jié) , 所以降低網(wǎng)絡 的偵聽能耗成為延長 W SN 生命期的特性因素和主 要手段 , 同時該場景下拓撲控制算法的設計還必須 符合傳統(tǒng)算法設計的 共性原則 8?；仡櫼酝嫦?事件驅 動 型網(wǎng) 絡 經(jīng)典 算 法

9、有 :STE M 算法 9、 AS CENT 算法 10等。本文就是在研究 ASCENT 算法啟 發(fā)機制思想的基礎上結合層次型拓撲控制分簇思想 改善設計了一種自適應的混合型拓撲控制算法 AHTC (Adapti v e H ybrid Topo l o gy Contro l 算 法。仿 真結果表明 , 改進后的算法較原有算法有更好的節(jié) 能性和穩(wěn)定性。本文針對的應用場合有以下特點 :節(jié)點規(guī)模 大。類似于建筑物狀態(tài)監(jiān)控、 森林防火或者生態(tài)保 護等隨機部署的節(jié)點場景。 ! 分布 密度大且不均 勻。假設部署的節(jié)點有一定的密度 , 即一個節(jié)點在 自己的通信范圍內至少覆蓋另一節(jié)點。 事件發(fā)生 的隨機性。

10、 #事件發(fā)生的低概率性。1 A SCENT 算法分析1. 1 ASCENT 算法的基本原理算法的前提假設 :節(jié)點密度足夠的大 ; ! 有一 個 CS MA MAC 協(xié)議或者 TDMA MAC 協(xié)議支持。 ASCENT (Adaptive Self Configuring s Ensor Net w orks Topo l o g ies 算法在 W SN 網(wǎng)絡中運行時包括觸 發(fā)、 建立和穩(wěn)定三個階段。觸發(fā)階段 , 在匯聚節(jié)點與 數(shù)據(jù)源節(jié)點不能正常通信時 , 匯聚節(jié)點向它的鄰居 節(jié)點發(fā)出求助信息 ; 建立階段 , 當節(jié)點收到鄰居節(jié)點 的求助消息時 , 通過一定的算法決定自己是否成為 活動節(jié)點 ,

11、 如果成為活動節(jié)點 , 就向鄰居節(jié)點發(fā)送發(fā) 布 鄰居聲明 %消息 , 同時這個消息是鄰居節(jié)點判斷 自身是否成為活動節(jié)點的因素之一 ; 穩(wěn)定階段 , 數(shù)據(jù) 源節(jié)點和匯聚節(jié)點間的通信恢復正常。網(wǎng)絡中活動 節(jié)點個數(shù)保持穩(wěn)定 , 從而達到穩(wěn)定狀態(tài)。1. 2 ASCENT 算法的狀態(tài)轉換機制在 ASCENT 算法中 , 節(jié)點始終處于下面四種狀 態(tài)中的任意一種 :睡眠 (SLEEP 、 偵聽 (PASSI VE 、 測試 (TEST 、 活動 (AC T I V E 。初始 , 一個隨機的定時器打開 , 任意節(jié)點在測試 階段初始化。當一個節(jié)點進入測試階段時候 , 它就 設定一個時間器 T, t 當 Tt

12、期滿的時候 , 發(fā)送 鄰居聲 明 %消息 , 節(jié)點進入活動狀態(tài)。如果在 Tt 到來之前 活動節(jié)點的數(shù)目超過了鄰居上限 (NT 或者如果平 均數(shù)據(jù)丟失率 (DL 高于在自己處于測試階段時的 點同時轉入了測試狀態(tài)。就選擇在 鄰居聲明 %消 息里節(jié)點 I D 高的節(jié)點成為活動節(jié)點?；顒庸?jié)點的 數(shù)目不能超過 NT 值。當一個節(jié)點進入偵聽態(tài)的時 候 , 它設置了一個定時器 Tp 。當 Tp 時間到的時候 , 節(jié)點進入休眠狀態(tài)。如果在 Tp 到來之前鄰居數(shù)目 低于 NT, 或者 DL 高于丟包 臨界值 (LT , 或 者 DL 低于丟包臨界值但是節(jié)點收到了一個來自于活動鄰 居的求助消息。節(jié)點就轉入到測試狀

13、態(tài)。當在偵聽 狀態(tài)時節(jié)點打開他們的射頻模塊 , 能夠監(jiān)聽到他所 有的活動鄰居傳送的包 , 但不傳送任何數(shù)據(jù)包。處 于偵聽和測試狀態(tài)的節(jié)點 , 持續(xù)刷新活動鄰居的數(shù) 目和數(shù)據(jù)丟失率的值。一個進入休眠態(tài)的節(jié)點關閉 射頻模塊 , 設置一個時間 Ts 用來度量休眠長度。當 Ts 到了的時候 , 節(jié)點轉入偵聽模式。一個節(jié)點一旦 進入活動狀態(tài) , 就在活動狀態(tài)繼續(xù)傳遞數(shù)據(jù)和路由 包直到它消耗 完能量為止。如果數(shù)據(jù)丟失 率高于 LT 時 , 活動的節(jié)點又開始發(fā)送求助消息。1. 3 ASCE NT 算法的局限性分析(1ASCENT 的應用場合實際上 ASCENT 算法只是提出了一種密集型網(wǎng) 絡局部自適應優(yōu)化的

14、方法。如果網(wǎng)絡規(guī)模增大的時 候由于算法基于鄰近發(fā)現(xiàn)原則 , 所以連起來的拓撲 都是一跳連接 , 使得網(wǎng)絡通信鏈路過于復雜 , 網(wǎng)絡中 有太多的活動節(jié)點。隨著網(wǎng)絡規(guī)模的增大能耗將大 大提升。(2 難以保證的連通性雖然算法中規(guī)定了一些鄰居域、 丟包率等來調 節(jié)活動節(jié)點的個數(shù) , 由于沒有考慮剩余能量等負載 平衡問題 , 當活動節(jié)點能量不足難以勝任轉發(fā)任務 時 , 網(wǎng)絡的連通性就很難得到保障。導致網(wǎng)絡能量 消耗不均勻。(3 狀態(tài)轉換機制的不足在 ASCE NT 算法中 , 一旦節(jié)點從測試態(tài)進入活 動態(tài)后就一直保持激活直到能量耗完為止 , 這樣就 造成了網(wǎng)絡能源的不必要浪費。特別是在事件驅動 型網(wǎng)絡中

15、。最重要的是要在節(jié)點偵聽與休眠之間找 到一種平衡策略。而算法中活動節(jié)點無法再進入休 眠狀態(tài)的機 制導致 全網(wǎng)能 耗加 大 , 甚至 出現(xiàn)割 裂 現(xiàn)象。2 AHTC 算法設計針對 ASCENT 算法中不足 , 本文提出了一種自 適應的混合型 拓撲控制算法 AHTC 算法 , 該算 法將 ASCE NT 的協(xié)同啟發(fā)機制應用到簇內和簇間通 ,429傳 感 技 術 學 報 第 23卷模事件驅動型網(wǎng)絡中去。2. 1 AHTC 算法的設計思想AHTC 算法在沿用 ASCENT 算法的原有機制的 基礎上引入分簇的思想 , 使得算法更適應于大規(guī)模 網(wǎng)絡。在測試狀態(tài)使用了一種動態(tài)的 延時避讓機 制 %。規(guī)定了活

16、動節(jié)點的時間域值 Ta 。2. 2 基本定義表C M:(CLUSTERME M BER 簇內節(jié)點。C H:(CL U STERHEAD 簇頭節(jié)點。E :i 節(jié)點 i 當前剩余能量。TEST 消息 :TEST 消息發(fā)送成功則節(jié)點發(fā)送包 含自身 I D 號的 HELLO 消息 , 表示自 身成為簇頭。 節(jié)點若已經(jīng)是簇頭 , 或者已經(jīng)屬于某一個簇 , 則不發(fā) 送 TEST 消息。節(jié)點信息 :一個節(jié)點的節(jié)點信息包括自身 I D 及 剩余能量值 E i 。CLUSTER 消息 :由 CH 節(jié)點發(fā)送 , 告知 C M 節(jié)點 C H 節(jié)點的 I D 與 En , 及該簇內部所有節(jié)點之間的鄰 居節(jié)點關系和 E

17、 i 。 收到該消息的 C M 節(jié)點記錄自身 處于哪一個簇 , 并確定鄰居節(jié)點 , 調整發(fā)送功率。 關聯(lián)節(jié)點 :一個 C M 節(jié)點可以同時屬于不同的 多個簇 , 即同時 收到兩 個或兩 個以上 的 CLUSTER 消息 , 這種節(jié)點稱為關聯(lián)節(jié)點 , 是連接不同的多個簇 的關鍵。一個節(jié)點一旦成為關聯(lián)節(jié)點 , 就要周期性 地向自身所處的各個簇頭節(jié)點發(fā)送 CONECTNODE 消息報告 , 報告自身的關聯(lián)的簇的信息。成簇概率 P :分簇算法參考文獻 11中提出的 隨機簇頭選擇算法 , 這種簇頭選舉方式十分簡單 , 僅 僅通過隨機競爭的方式完成 , 實驗證明單個節(jié)點發(fā) 送探測消息的平均次數(shù)接近 e 次

18、 , 這在實際網(wǎng)絡成 簇中是可以接受的。在網(wǎng)絡中選舉剩余能量多的節(jié) 點作為簇頭也有利于延長傳感器節(jié)點的生存時間。 P 與節(jié)點 n 的剩余能量成正比 , P =k E r /E m 。 E r 節(jié) 點 n 當前剩余能量。 E m 是節(jié)點 n 初始最大能量。 HELP 消息 :用來把節(jié)點由偵聽 狀態(tài)轉入測試 狀態(tài)或由測試狀態(tài)轉入活動狀態(tài)的直接依據(jù)。 時間域值 Ta :在時間 Ta 內如果沒有消息轉發(fā)。 則認為該節(jié)點可以由激活狀態(tài)轉入休眠狀態(tài)。 2. 3 AHTC 算法的整體設計步驟(1 STEP1分簇節(jié)點部署以后 , 在初始時刻任意一 個節(jié)點 n 首先以概率 P 發(fā)送 TEST 消息。若發(fā)送 TE

19、ST 消息 不成功 , 則進人偵聽狀態(tài) ; 若發(fā)送成功 , 就將自身設 置為簇頭 (C H , 并使用最大發(fā)送功 率向周圍發(fā)送 TEST 消息 , 則重 新選舉。其他節(jié)點 若接收到 這個 H ELLO 消息 , 就向節(jié)點 n 周期性地回復 ACK 消息 , 表明自己加人該簇。 ! 節(jié)點 n 接收到其它節(jié)點回復 的 ACK 消息 , 統(tǒng)計自身的鄰居節(jié)點集 N, 然后形成 一個包含自身 I D 、 剩余能量及簇內所有節(jié)點 I D 和 剩余能量的簇消息 CLUSTER 。并 向所有簇內節(jié)點 C M 發(fā)布此消息。收到 CLUSTER 消息的節(jié)點 , 自己 維護自身 的鄰居集合。如果一 個 C M 收到

20、了 多個 CLUSTER 消息 , 則表明自己是關聯(lián)節(jié)點 , 這時向簇 頭發(fā) CONECTNODE 消息。當分簇結束后 , 全網(wǎng)的節(jié)點被分為簇內節(jié)點、 關 聯(lián)節(jié)點和簇頭節(jié)點。每個節(jié)點維護的本地信息包括 鄰居節(jié)點信息 , 此外 , C H 還需維護一個關聯(lián)節(jié)點信 息 , 而關聯(lián)節(jié)點則需多維護一個簇頭節(jié)點信息。 (2 STEP2簇內通信簇內通信采用局部的 ASCE NT 算法 , 不同的是 從數(shù)據(jù)源發(fā)起求助信息 , 并考慮節(jié)點剩余能量問題。 初始化階段 , 所有節(jié)點進入測試階段。開始由任一 數(shù)據(jù)源發(fā)起 HELP %消息。發(fā)給節(jié)點剩余能量較為高 的鄰居節(jié)點。 ! 鄰居節(jié)點加入活動節(jié)點一起來轉發(fā) 數(shù)據(jù)

21、 , 如此反復直到本簇的簇頭節(jié)點加入活動節(jié)點。 規(guī)則 1 如果節(jié)點發(fā)現(xiàn)自己的鄰居中有簇頭節(jié) 點 CH 則 直 接選 擇 該節(jié) 點 充 當活 動 節(jié) 點并 轉 到 STEP3的第一步 , 如果節(jié)點發(fā)現(xiàn)自己的鄰居中沒有 CH 節(jié)點 , 但是有關聯(lián)節(jié)點 , 則選擇關聯(lián)節(jié)點充當活 動節(jié)點并轉到 STEP3的第二步。規(guī)則 2 在 規(guī)則 1的 基礎 上 , 如果 節(jié) 點發(fā) 出 HELP %消息之后 , 發(fā)現(xiàn)丟包率仍然高于丟 包臨界 (DL, 則選擇剩余能量次高的鄰居 , 要求其加入活 動節(jié)點。依次類推。直到發(fā)現(xiàn)鄰居數(shù)目高于鄰居臨 界 (NL為止。規(guī)則 3 如果發(fā)現(xiàn)有多個簇頭或者關聯(lián)節(jié)點的 情況 , 選擇剩

22、余能量權重大的來觸發(fā)。(3 STEP3簇間通信在簇間仍然使用 ASCENT 規(guī)則 , 來完成興趣數(shù) 據(jù)的轉發(fā)。 當某一簇頭節(jié)點 C H 加入活動節(jié)點之 后 , 向 sink 節(jié)點方向的關聯(lián)節(jié)點發(fā)布 H ELP %消息。 選擇剩余能量大的關聯(lián)節(jié)點加入到網(wǎng)絡中。 ! 然后 該關聯(lián)節(jié)點再向 si n k 方 向的簇 頭發(fā)送 H ELP %消 息。如此反復直到把消息傳送給 si n k 節(jié)點。規(guī)則 4 對于孤立簇 , 如果 C H 沒有收到 C M 的 CONECTNODE 消息時 , 則要求所有的 C M 探測自身 的鄰居節(jié)點 , 加入關聯(lián)節(jié)點。(4 STEP4拓撲維護階段C M430中有 C H

23、節(jié)點失效則重新進入簇頭選舉和全網(wǎng)待定 狀態(tài)。也即等待網(wǎng)絡中隨機事件的發(fā)生。經(jīng)過 AHTC 算法之后 , 得到如圖 1所示的 AHTC算法形成拓撲圖。 圖 1 兩種算法的形成拓撲圖對比2. 4 AHTC 算法的狀態(tài)轉換機制 AHTC 的狀態(tài)轉換機制是在 ASCE NT 算法狀態(tài) 轉換機制的基礎上 , 做如下改動 : 將原來的固定測 試狀態(tài)時間 T t 改為一個動態(tài)的延時避讓機制。 ! 在 節(jié)點一進入活動狀態(tài)的時候 , 啟動一個時間計數(shù)器 Ta , 等 Ta 值到來之前沒有任何消息轉換時節(jié)點轉入 休眠狀態(tài)。之所以引入 延時避讓機制 %是因為原算法中 Tt 等待時間是一個固定參數(shù) , 當節(jié)點從偵聽階

24、段轉 入測試階段時定時計數(shù)器 T t 值開始計時 , 如果在此 期間活動節(jié)點的數(shù)目沒有超過鄰居上限 (NT 或者 平均數(shù)據(jù)丟失率 (DL 仍低于在自己處于測試階段 時的平均數(shù)據(jù)丟失率時節(jié)點轉入活動狀態(tài)。這樣就 會導致不管節(jié)點剩余能量高低或者鄰居節(jié)點多少只 要 Tt 值到來就要強迫節(jié)點進入活動狀態(tài) , 使得能量 很低的節(jié)點仍要承擔轉發(fā)任務 , 導致通信質量得不 到保證 , 網(wǎng)絡能量消耗不均。為避免上述情況發(fā)生 , 綜合考慮節(jié)點剩余能量 和節(jié)點鄰居數(shù)目等因素給出 T t 參數(shù)一般化定義 :令 T t=(1-E i/E m &N i+R, 其中 E i 是節(jié)點的 剩余能量 , E m 是該節(jié)

25、點的最大能量 (電池充滿時的 能量 , N i 是節(jié)點鄰居個數(shù) (這里不考慮數(shù)據(jù)延遲等 因素 , R 為時間補償因子。由于算法的應用場合是 大規(guī)模密集型網(wǎng)絡 , 為了避免節(jié)點分布不均導致的 節(jié)點間通信干擾加入 N i 參數(shù)來調整 T t 值。具體實現(xiàn)方法如下 :當一個節(jié)點進入測試階段 時 , 算法自動計算一個 Tt 值。由公式可知 , 剩余能量 越多鄰居節(jié)點越少的節(jié)點 Tt 值越小 , 越快速進入活 動節(jié)點狀態(tài)。而對于剩余能量雖多但鄰居數(shù)目很多 的節(jié)點來說 , 會有效的延長 Tt 值 , 以避免在節(jié)點密集 區(qū)域出現(xiàn)過多的活動節(jié)點。抑制通信干擾。此外 , 對 于剩余能量不多但鄰居節(jié)點數(shù)很少的節(jié)點

26、來說 T t 值 也很小 , 這樣可以保證在節(jié)點分布稀疏區(qū)域仍有節(jié)點, 節(jié)點后 , 就向該節(jié)點的所有鄰居節(jié)點公布一個 鄰居 聲明 %消息 , 如果在 Tt 值到來之前某節(jié)點收到了一個 自身鄰居的 鄰居聲明 %消息就返回到偵聽狀態(tài)。這 樣就有效的促進了剩余能量多且鄰居節(jié)點數(shù)目較少 的節(jié)點優(yōu)先進入活動狀態(tài) , 使得全網(wǎng)能耗更加均衡。整個網(wǎng)絡節(jié)點都按照 ASCENT 算法四種狀態(tài)不 停的循環(huán) , 并加入一個時間域 Ta 值 , 即如果在這個 時間內活動節(jié)點不再轉發(fā) 數(shù)據(jù)則主動進入 休眠狀 態(tài)。這樣就大大節(jié)省了網(wǎng)絡資源的消耗 , 使得算法 更加適用于事件驅動型網(wǎng)絡。這里 Ta 的值要通過實際事件發(fā)生概

27、率的大小等因素而定 , 在此不作為 本文討論重點。兩種算法的狀態(tài)轉換圖對比如圖 2所示。圖 2 兩種算法的狀態(tài)轉換圖 對比3 仿真與性能分析為了評價和分析 AHTC 算法與 ASCE NT 算法性 能優(yōu)劣 , 通過 OMNE T +12仿真工具 對其進行模 擬。利用 NED 和 I N I 配置文件描述下面實驗環(huán)境 :N 個節(jié)點隨機部署在 100m &100m 的正方形事件區(qū)域 內。隨機選擇 1個節(jié)點作為匯聚節(jié)點 , pN 個節(jié)點作 為源節(jié)點 , 源節(jié)點以速率 v =5kpbs 勻速獲知數(shù)據(jù)并 發(fā)往匯聚節(jié)點。每個節(jié)點通信半徑 50m , 節(jié)點初始 能量 10J , 節(jié)點偵聽能耗 0.

28、1J 。 實驗中不考慮節(jié)點 移動性和報文傳輸延時 , 并且忽略節(jié)點接收報文及處 理器的能耗。按照文獻 4對 ASCNET 算法參數(shù)設 置如下 :DL=4, LT =20%, T:t Tp :Ts=2:5:30, Tt=2s 。 在 AHTC 算法中取 T t 時間補償因子 R=1s , 其 它參數(shù)仍采用原算法中固定參數(shù)。為了盡量忽略由 于 Ta 值導致的網(wǎng)絡性能不同 , 設 Ta=20Tp 。節(jié)點信 號強度之比用距離平方的反比來表示。在上述環(huán)境 中對 ASCENT 與 AHTC 算法做如下對比仿真 : 興趣 事件發(fā)生概率 P 的確定實驗 , 通過對網(wǎng)絡丟包率的分 析 , 確定在 P =0. 0

29、8的情況下來進行兩種算法的對 比 ; ! 在仿真模型下不斷修改節(jié)點數(shù)目 , 判斷兩種算 法對網(wǎng)絡生命期的影響 ; 在給定的源數(shù)據(jù)包情況 下 , 判斷節(jié)點丟包率的隨節(jié)點數(shù)目增大的變化情況來3. 1 興趣事件發(fā)生概率 P 仿真分析 興趣事件發(fā)生概率 P 作為 W SN 的重要特征參 數(shù) , 體現(xiàn)了 W SN 的應用相關 性。本實驗分 析 P 變 化對 AHTC 算 法的 影 響。為 了 不 失一 般 性 P 從 0 010. 4之間間隔 0. 1分別取 0. 08、 0. 18、 0. 28、 0. 38取值時 , 4條變化數(shù)據(jù)線如圖 3所示。 4條數(shù)據(jù) 線表明 P 愈小 , 則 AHTC 所獲

30、W SN 生命期愈大 , 這 是因為隨著 P 降低 , 偵聽開銷的增幅低于興趣數(shù)據(jù) 傳輸開銷的降幅 , 所以引發(fā)了 W SN 生命期的增加。 從圖 3中可以看到 , 隨著節(jié)點數(shù)增加 , 4條數(shù)據(jù)線均 呈上升勢態(tài) , 這是由于節(jié)點分布密集必導致單個節(jié) 點的平均簇內能耗降低 , 節(jié)點進入休眠態(tài)的幾率大 大提高 , 從而引起 W SN 生命期增長。此外 , 從圖 3還可發(fā)現(xiàn)隨著節(jié)點數(shù)逐漸增長不同 P 值下生命期 差異愈加顯著 , 這是由于在相同的節(jié)點數(shù)增加率的 基礎上 , P 值越大網(wǎng)絡中的活動節(jié)點數(shù)目就越多 , 網(wǎng) 絡偵聽能耗就越大 , 網(wǎng)絡生命期就越短。這種現(xiàn)象 隨著 P 值的減小而趨于 緩和。

31、以下仿 真使用 P =0. 08。 圖 3 P 對網(wǎng)絡生命期的影響3. 2 網(wǎng)絡節(jié)能性仿真分析仿真中采用一半節(jié)點死亡的時間作為網(wǎng)絡生存 時間的評價標準。因為若網(wǎng)絡中一半節(jié)點死亡 , 剩 余節(jié)點的能量已經(jīng)很低 , 而網(wǎng)絡的連通度也無法有 效保證。網(wǎng)絡生存時間的對比如圖 4所示。 AHTC 的網(wǎng)絡生存期明顯高于 ASCENT 。特別是隨著節(jié)點 數(shù)目的增多 , ASCENT 算法下網(wǎng)絡生存期增幅越來 越小 , 這是因為一方面隨著網(wǎng)絡節(jié)點數(shù)目的增多 , 處 于偵聽與活動狀態(tài)節(jié)點過多 , 造成了網(wǎng)絡不必要的 消耗。另一方面由于活動節(jié)點無法進入休眠狀態(tài)而 導 致大 部分 節(jié) 點過 早 死亡 , 出現(xiàn) 網(wǎng)

32、絡割 裂現(xiàn) 象。 AHTC 算法在考慮剩余能量的基礎上加入分簇思想 使得節(jié)點有效選擇鏈路而避免了過多節(jié)點加入到信 息轉發(fā)中來 , 同時也達到了負載均衡的目的。此外 , 由于 T t 參數(shù)由原來的固定參數(shù)變?yōu)橐环N動態(tài)的時 間機制 , 使得剩余能量多且鄰居數(shù)目少的節(jié)點優(yōu)先生命期。而 Ta 參數(shù)的加入 , 很好的避免了節(jié)點早死現(xiàn)象。分析結果表明 AHTC 算法更適應于大規(guī)模事 件驅動型網(wǎng)絡。圖 4 AHTC 與 ASCE N T 網(wǎng)絡生存期對比3. 3 網(wǎng)絡穩(wěn)定性仿真分析仿真中不斷增加模型節(jié)點數(shù)目參數(shù) , 在與其相 應的 W SN 網(wǎng)絡生存期內統(tǒng)計兩種算法情況下導致 的 S i n k 節(jié)點收到數(shù)據(jù)

33、包數(shù)目總和。由圖 5可知 , 隨 著節(jié)點數(shù)目的增加 , AHTC 算法下 匯聚節(jié)點收到的 數(shù)據(jù) 包數(shù) 在相 應的 增多 , 而且 增幅 較大。而 AS CE NT 算法下 S i n k 節(jié)點收到的數(shù)據(jù)包數(shù)目在節(jié)點數(shù) 少于 100時還有一些增幅 , 但是當節(jié)點數(shù)接近或高 于 100以后 , S i n k 節(jié)點收到的數(shù)據(jù)包數(shù)目已經(jīng)基本 上保持不變 , 即增幅趨于零。這也進一 步表明 AS CE NT 算法 在 網(wǎng) 絡 規(guī) 模 逐 漸 增 大 時 丟 包 率 急 劇 上升。圖 5 AHTC 與 ASCENT 數(shù)據(jù)包數(shù)目對比仿真分析結果表明 , AHTC 算 法延長了網(wǎng)絡生 命周期 , 減少了網(wǎng)絡

34、丟包率。改善了原算法的節(jié)能 性和穩(wěn)定性。4 結束語本文在 ASCNET 算法的基礎上 , 改善設計了一 種適用于大規(guī)模事件驅動型網(wǎng)絡的混合型拓撲控制 算法 -AHTC 算法。該算法結合層次型拓撲算法的 分簇思想以及節(jié)點 延時避讓機制 %理念 , 擴大了原 算法的應用場合 , 使網(wǎng)絡中剩余能量高的節(jié)點充當 活動節(jié)點 , 延長了 網(wǎng)絡生命周期 , 減少了網(wǎng) 絡丟包 ,第 3期 李少春, 程良倫等: 一種自適應的混合型無線傳感器網(wǎng)絡拓撲控制算法 Italy: A CM Press 2001: 70- 84. , 6 433 低了全網(wǎng)能耗。 下一步要做的工作: 一方面根據(jù)實際情況給出 一種測試狀態(tài)時間

35、域 T t更有效的計算方法。本文 只是針對原算法中固定參數(shù)作出初步優(yōu)化。另一方 面提出一種符合實際情況的動態(tài)活 動節(jié)點時間域 T a的計算方法, 使算法更趨于合理性和完善性。 參考文獻: 1 2 楊賀, 張樹東, 孫利民. 無線傳感器網(wǎng) 絡的拓撲控制機 制 J . 計算機科學, 2007 34 ( 1 : 36 - 38. , K ub isch M, K arl H, W ol isz A, et a. D istribu ted A lgorithm s for l Tran s iss ion Pow er C on trol in W ireless S ensor N etw ork

36、s C / / m I EEE W CNC 2003 N ew O rleans Lou isiana, M arch, 2003. , , 3 4 L i N, H ou J C. Topology C ontrol in H eterogeneous W ireless N et w orks Problem s and Solut ion s C / / I FOCOM, 2004 : N . L i N, H ou J C, Sha L. D esign and A nalys is of an M ST based To pology C ontrol A lgorithm A .

37、In Proc of Tw en ty S econd A nnu : . a l Joint C onference of the IEEE Co m pu ter and C ommun ications Societ ies( I NFOR C0M 2003 . S anfrancisco CA: , 2003 1702- 1712. : 5 Xu Y, H eidem ann J E strinn G eography in for ed En ergy C onser . m vation for A d H oe R out ing C / /P roc. of the 7th A

38、 nnu al In terna tional Con ference on M ob ile Com pu ting and N et ork ingr R om e, w . I EEE Press , H einzel an W R, Chand rakasan A, Balakr ishn an H. A n A pp lica m t ion specific Protoco l A rch itecture for W ireless M icrosen sor N et w ork s J . IEEE T ransact ion s on W ireless Commun ications O cto , ber 2002 1 ( 4 : 660- 670. , , 7 Zhang B,