魯曉輝

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

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

魯曉輝

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

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

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

引言

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

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

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

1 LEACH 算法和 PEGASIS 算法

1.1 LEACH 算法

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

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

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

1.2 PEGASIS 算法

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

2 新算法的提出

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

2.1 新算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

dsj＞dsi（4）

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

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

3 新算法的仿真與驗(yàn)證

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

仿真參數(shù)表

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

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

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

4 結(jié)束語(yǔ)

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

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

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

[3]解 熒 ， 韓 陽(yáng) 龍 ， 趙 剛 等.偽 三 維 的 地 理 位 置 無(wú) 線 傳 感 器 網(wǎng) 絡(luò)路 由 算 法[J].計(jì) 算 機(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].計(jì) 算 機(jī) 測(cè) 量 與 控 制.2012，20（02）：490-493.

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

TP393

：B

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

2014-05-10

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