基于扇形區(qū)域的無線傳感器網(wǎng)絡(luò)路由算法研究

魯曉輝

（三門峽職業(yè)技術(shù)學(xué)院 信息傳媒學(xué)院，河南 三門峽 472000）

基于扇形區(qū)域的無線傳感器網(wǎng)絡(luò)路由算法研究

魯曉輝

（三門峽職業(yè)技術(shù)學(xué)院 信息傳媒學(xué)院，河南 三門峽 472000）

基 于對經(jīng) 典分 簇算法 LEACH 和 PEGASIS 的 研究，提出 一種 新的分 簇路 由算法 。 該算 法在 簇頭 選 擇機 制上 對 LEACH 算 法作 了 一定 的改 進，重點考 慮了 節(jié) 點剩余 能 量 等參數(shù) ，有效 避 免 了低能 量 節(jié) 點 被選 為 簇 頭 。 隨 著 與 匯聚節(jié)點距離的增大，簇的規(guī)模也逐漸增大。同時，將網(wǎng)絡(luò)劃分為多個扇形區(qū)域，每一扇區(qū)內(nèi)部節(jié)點間的數(shù)據(jù)傳輸采用多跳方式進行。 通過對算法驗證，與 LEACH 算法、PEGASIS 算法比較，新算法對網(wǎng)絡(luò)生存時間的延長明顯。

路由算法；多跳通信；無線傳感器網(wǎng)絡(luò)；分簇

引言

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，簡稱 WSN）是采用大量傳感器組成無線網(wǎng)絡(luò)，目前被廣泛應(yīng)用于環(huán)境監(jiān)控、醫(yī)療護理、目標(biāo)跟蹤等多個領(lǐng)域，主要功能包括采集監(jiān)控區(qū)域信息，將信息進行處理并返回網(wǎng)絡(luò)擁有者。受傳感器構(gòu)造與部署環(huán)境的限制，WSN 網(wǎng)絡(luò)中各節(jié)點攜帶能量受到極大的限制 ，對 節(jié) 點 進 行能 量 補 充 也 存 在極 大 困 難[1]。 因 此 ，通過對協(xié)議的研究， 如何利用有限的能量資源，設(shè)計出能耗低、網(wǎng)絡(luò)生命周期長的新路由算法，是目前傳感器網(wǎng)絡(luò)研究的主要方向。

無線傳感器網(wǎng)絡(luò)的路由協(xié)議分為平面路由協(xié)議和分層路由協(xié)議兩種。由于通信損耗能量與傳送的數(shù)據(jù)量和到達目標(biāo)的距離的平方成正比,采用基于分層的路由算法與采用平面路由算法相比，前者具 有 更 好 的 適 應(yīng) 性 和 節(jié) 能 性[2]， 在 分 層 路 由 算 法 中 ，比 較 具 有 代 表 性 的 有 LEACH 算 法[3-4]，PEGASIS 算法[5]等 。 在 LEACH 算 法 中,節(jié) 點 組 織 成 多 個 簇 ， 每 一個簇的簇頭負責(zé)融合來自簇內(nèi)不同成員產(chǎn)生的數(shù)據(jù),并 轉(zhuǎn) 發(fā) 給 匯 聚 節(jié) 點 （Sink）。 PEGASIS 算 法 針 對LEACH 算法進行了改進， 為節(jié)約能量每個節(jié)點僅與其相鄰節(jié)點進行信息傳遞，對匯聚節(jié)點的信息傳遞僅由鏈?zhǔn)坠?jié)點完成。 通過比較可知 LEACH 算法的分簇能夠降低網(wǎng)絡(luò)的延遲并提升效率，PEGASIS算法采用的多跳數(shù)據(jù)路由，主要的優(yōu)勢在于均衡不同節(jié)點的能量消耗，在傳輸?shù)耐瑫r融合數(shù)據(jù)，減少傳輸?shù)臄?shù)據(jù)量。

筆者 將 LEACH 算法和 PEGASIS 算 法 的 優(yōu)點有機結(jié)合在一起，提出了一種新的分簇路由算法。新算法的主要優(yōu)點包括：（1） 減少網(wǎng)絡(luò)開銷；（2）平衡不同節(jié)點的能量消耗；（3）有效延長網(wǎng)絡(luò)存在時間。

1 LEACH 算法和 PEGASIS 算法

1.1 LEACH 算法

LEACH 算法是目前應(yīng)用較廣泛的低功耗自適應(yīng)算法。算法的核心是簇頭節(jié)點的確定是隨機選擇的結(jié)果，隨著每周期簇頭節(jié)點的變化，將網(wǎng)絡(luò)能量負載進行分配，最終達到降低能量消耗延長網(wǎng)絡(luò)生命周期的目的。

LEACH 將每次簇頭選擇視為一輪， 在一輪開始的時候， 所有節(jié)點均隨機 生成一個介于 0-1 的數(shù)，最終得到的數(shù)比閾值 T（n）小的，即為簇頭。

其中，p 為預(yù)設(shè)的簇頭百分比，r為當(dāng)前的輪數(shù)，G 是最近 1／p 輪沒有成為簇頭的節(jié)點集合。 簇頭的選擇基本上可以確保每個節(jié)點成為簇頭的概率相當(dāng)，當(dāng)簇頭確定后，其余節(jié)點根據(jù)距離選擇加入最近的簇頭，并通過簇頭傳遞信息。

1.2 PEGASIS 算法

PEGASIS 算法的核心思想 是利用貪婪算 法 生成一條由所有節(jié)點組成的單鏈，節(jié)點僅與相鄰節(jié)點傳遞消息，每個節(jié)點完成兩個工作：第一，接收上一節(jié)點的信息；第二，將信息與自身數(shù)據(jù)融合，將融合后的信息發(fā)送到下一節(jié)點，直至到達簇頭，最終由簇頭將信息傳遞給匯聚節(jié)點，采用此算法各節(jié)點的負載較為均衡。

2 新算法的提出

本文結(jié)合兩個算法的優(yōu)點，提出改進算法，新算法通過構(gòu)建大小不同的簇來均衡網(wǎng)絡(luò)中節(jié)點的能量消耗，即靠近匯聚節(jié)點的簇半徑相對較小，隨著與匯聚節(jié)點距離的增加，簇半徑也相應(yīng)增加。這樣，距匯聚點近的簇頭能夠保留更多的能量用于簇間的數(shù)據(jù)的轉(zhuǎn)發(fā)[5]。 由于 PEGASIS 在選擇最近的節(jié)點時會自動排除已經(jīng)在鏈路中出現(xiàn)過的節(jié)點，這樣必將導(dǎo)致中繼節(jié)點的距離變大，所以相鄰節(jié)點間的長鏈就不可避免，最終導(dǎo)致能量消耗增大，為了避免這種情況，本文算法將目標(biāo)區(qū)域劃分為多個扇形區(qū)域，簇頭節(jié)點只與本區(qū)域內(nèi)的其他簇頭節(jié)點形成多跳路由，這樣可以有效降低節(jié)點間鏈路的長度，減少能量消耗。

2.1 新算法描述

在改進的新算法中，以基站為頂點，將目標(biāo)區(qū)域劃分成 n 個扇形區(qū)域， 扇形區(qū)域的編號從 1-n，每個區(qū)域內(nèi)節(jié)點的 ID 和所屬的扇形區(qū)域的編號有關(guān)，例如：在扇形區(qū)域 1 內(nèi)的所有節(jié)點編號均為 n1,扇形區(qū)域 2 內(nèi)的所有節(jié)點編號均為 n2， 依次類推，第 n 個扇形區(qū)域的節(jié)點編號為 nn, 用一張 TABLE表來記錄節(jié)點的 ID 信息。

（1）簇頭選擇的準(zhǔn)備工作：

本算法的簇頭選擇機制在 LEACH 算法簇頭選擇機制的基礎(chǔ)上增加節(jié)點剩余能量的判定，主要目的在于避免低能節(jié)點被選為簇頭。首先需要計 算 閾 值 T(n)[4],若 節(jié) 點 的 隨 機 生 成 數(shù) 大 于 T （n）則直接淘汰，其余節(jié)點被確定為候選簇頭，等待進行繼續(xù)篩選。

其 中 ，Ecurrent 代 表 節(jié) 點 剩 余 能 量 ；Eaverage代表節(jié)點平均剩余能量， 其余參數(shù)與 LEACH 算法相同。

（2）簇頭的確定與簇的形成

候選簇頭確定后，將通過競爭機制確定該輪的簇頭,首先，確定候選簇頭到匯聚節(jié)點的近似距離。具體做法是由匯聚節(jié)點通過給定功率發(fā)送廣播信號 ， 各 候 選 簇 頭 根 據(jù) 接 收 信 號 的 強 度 估 算 出 距 離[5]，計為 dsi。

第二，將近似距離帶入公式（3）計算每個候選節(jié)點的簇半徑 Ri。

其 中 ，dmax與 dmin分 別 代 表 候 選 簇 頭 距 離 匯 聚 節(jié)點的最遠與最近距離,R0為預(yù)設(shè)的最大簇半徑,C 為控制參數(shù)。

以此公式計算得到的簇半徑將以匯聚點為圓心向外逐漸擴大，最終結(jié)果是在匯聚點附近形成范圍較小包含節(jié)點較少的小型簇，而在聚會據(jù)點較遠區(qū)域形成范圍較大包含節(jié)點數(shù)目較多的大型簇。這樣距離匯聚點越近，簇頭能夠保留越多的能量用于簇間的數(shù)據(jù)轉(zhuǎn)發(fā)，從而可以延長網(wǎng)絡(luò)的壽命。

第三，確定簇半徑后，各候選簇頭向自身半徑Ri范圍發(fā)送競爭申請，申請應(yīng)包含自身能量剩余信息。 如區(qū)域能仍有其余候選節(jié)點，則能量剩余較多的成為簇頭，如區(qū)域內(nèi)無其他候選節(jié)點，則直接成為簇頭，并廣播簇頭確認信息。 簇頭確定后，其余節(jié)點按照最近原則加入最近的簇。最終形成如圖1所示的結(jié)構(gòu)。

圖1 簇結(jié)構(gòu)圖

（3）簇內(nèi)通信與簇間通信

簇內(nèi)所有節(jié)點收集與處理的信息直接通過簇頭向外發(fā)送，簇內(nèi)通信由簇頭為每個成員節(jié)點分配通信時隙，并存儲在 TDMA 時隙表 中，以確保簇內(nèi)通信的穩(wěn)定性。

簇間通信以多跳的形式進行，簇頭節(jié)點將收集到的成員節(jié)點信息進行融合后，發(fā)送給其上行簇頭節(jié)點。上行簇頭節(jié)點確認需要滿足三個條件。

第一，上行節(jié)點與下行節(jié)點均為簇頭節(jié)點且必須在同一區(qū)域，即在 TABLE 表中表明，兩個節(jié)點在同一扇區(qū)，具有相同的 ID 頭。

第二，上行節(jié)點到匯聚源的距離要小于下行節(jié)點 ， 即 上 行 節(jié) 點 Sj與 下 行 節(jié) 點 Si需 滿 足 公 式（4）。

dsj＞dsi（4）

第 三 ，對 于 節(jié) 點 Si,在 相 同 扇 區(qū) 內(nèi) ，滿 足 公 式 （4）的所有簇頭節(jié)點中，Sj距離其最近。

每個簇頭均擁有且只有一個上行節(jié)點，形成節(jié)點鏈，鏈條的最終指向匯聚節(jié)點。 每個節(jié)點直接將數(shù)據(jù)傳遞到其上行節(jié)點，最終匯聚節(jié)點得到各節(jié)點的融合數(shù)據(jù)，并進行處理。

3 新算法的仿真與驗證

對于新算法性能指標(biāo)的評價， 采用與 LEACH算法、PEGASIS 算法對比的形式進行， 各項環(huán)境配置如下表所示， 利用 Matlab 仿真工具進行仿真實驗,仿真結(jié)果如下。

仿真參數(shù)表

圖 2 顯示了 LEACH 算法，PEGASIS 算法 和 本文改進的新算法（圖中用本文算法代表）出現(xiàn)第一個死亡節(jié)點時的通信輪數(shù)。圖3是在不同的通信輪數(shù)下，三種算法存活節(jié)點個數(shù)的仿真結(jié)果。 對結(jié)果進行分析， 對比算法的首節(jié)點死亡時間分別在 264輪和 447 輪左右， 節(jié)點 100%死亡時的輪數(shù)分別在625 和 700 附近。 本文的算法出現(xiàn)第一個死亡節(jié)點在 522 輪左右，節(jié)點全部死亡在 714 輪左右。 本文算 法 的 通 信 輪 數(shù) 明 顯 高 于 LEACH， 稍 高 于PEGASIS。 綜合以上仿真結(jié)果，新算法在生存時間的提升上有較大改善。

圖2 網(wǎng)絡(luò)中第一個節(jié)點死亡的通信輪數(shù)

圖3 節(jié)點存活數(shù)目圖

4 結(jié)束語

提出了一種新的分簇路由算法，新算法以基站為頂點，將目標(biāo)區(qū)域劃分成多個扇形區(qū)域。采用不等簇結(jié)構(gòu)來成簇，簇的覆大小隨著距離基站的遠近不同而改變，簇內(nèi)節(jié)點將自身信息發(fā)送給簇頭節(jié)點，在簇頭節(jié)點進行融合處理。簇頭節(jié)點與本扇形區(qū)域內(nèi)的其他簇頭節(jié)點形成多跳通信路徑將數(shù)據(jù)傳給匯聚節(jié)點，這樣能夠有效避免信息傳遞中長鏈的形成，降低能量消耗，減少傳輸延遲。本文是在網(wǎng)絡(luò)數(shù)據(jù)傳輸可以進行數(shù)據(jù)融合的基礎(chǔ)上，設(shè)計了一種有效的路由算法來降低能耗，優(yōu)化網(wǎng)絡(luò)生存時間，但對于簇頭節(jié)點進行數(shù)據(jù)處理的具體方法并沒有涉及，下一步工作重點是進一步提升簇頭節(jié)點數(shù)據(jù)融合的效率。

[1]李 建 中 ，李 金 寶 ， 石 勝 飛.傳 感 器 網(wǎng) 絡(luò) 及 其 數(shù) 據(jù) 管 理 的 概念 、 問 題 與 進 展[J].軟 件 學(xué) 報 ，2003,14（10）：1717-1727.

[2]張 源 .一 種 基 于 LEACH 協(xié) 議 的 節(jié) 能 型 分 簇 路 由 算 法[J].計算機與現(xiàn)代化，2009（12）：133-136.

[3]解 熒 ， 韓 陽 龍 ， 趙 剛 等.偽 三 維 的 地 理 位 置 無 線 傳 感 器 網(wǎng) 絡(luò)路 由 算 法[J].計 算 機 工 程 與 應(yīng) 用 ，2013（22） ：63-67.

[4]HeinzelmanW R,Chandrakasan A P,Balakrishnan H. Anapp lication-specific protocol architecture for wireless microsensor networks [J].IEEE Transactions on W irelessCommunications(S1536-1276),2002,1(4):660-670.

[5]米奕萍,高媛.基于蟻群優(yōu)化的 WSN 能耗均衡鏈狀路由協(xié)議[J].計 算 機 測 量 與 控 制.2012，20（02）：490-493.

（責(zé)任編輯 梁紅艷）

TP393

：B

：1671-9123（2014）03-0114-03

2014-05-10

魯曉輝（1980-），男，河南三門峽人，三門峽職業(yè)技術(shù)學(xué)院信息傳媒學(xué)院講師。