摘要：在研究無線傳感器網(wǎng)絡低能耗自適應分簇路由算法LEACH等路由協(xié)議基礎上,，提出了無線傳感器網(wǎng)絡的動態(tài)拓撲能量有效成簇算法：其主要內(nèi)容包括：1、采用引入能量因子的低復雜度簇頭選擇算法,。2,、支持部分節(jié)點移動的拓撲動態(tài)的網(wǎng)絡。3,、在數(shù)據(jù)傳輸上通過多跳方式進行信息路由,。理論和仿真結果證明，本算法相對于LEACH算法,，在網(wǎng)絡生命周期上得到了提高,。

1 引言

無線傳感器網(wǎng)絡（Wireless Sensor Network,，WSN）作為下一代的信息獲取技術引起了世界各國的重視，日漸成為國內(nèi)外學術機構的研究熱點,。無線傳感器網(wǎng)絡通常是由大量傳感器節(jié)點通過射頻通信形成的一個自組織網(wǎng)絡系統(tǒng),。它通過對被監(jiān)測對象目標信息的感知，獲取和處理,，提供給管理者以有用的信息,，可以廣泛地應用于智能家居、醫(yī)療衛(wèi)生,、工業(yè)控制,、農(nóng)業(yè)種植、軍事預警以及防洪救災等特殊場合,。但是,，WSN與移動Ad Hoc網(wǎng)絡（MANET）是有著很大區(qū)別的，它們的通信方式,、通信目的和網(wǎng)絡拓撲很不相同,，尤其在能量來源方面，WSN是采用電池供電,，路由算法對傳感器網(wǎng)絡的存活周期起著重要的影響,，所以移動Ad Hoc網(wǎng)絡的路由協(xié)議不能完全適應于WSN，我們需要單獨研究適合于無線傳感器網(wǎng)絡的通信協(xié)議,。

2動態(tài)拓撲能量有效成簇算法

針對層次路由協(xié)議中存在的各種問題,，本文提出了適用于WSN的動態(tài)拓撲能量有效成簇算法(DTEE)。此算法引入基于能量因子的低復雜度的簇頭選擇機制,，同時通過協(xié)議的設計使其支持節(jié)點部分離去或有新節(jié)點加入的拓撲動態(tài)傳感器網(wǎng)絡,。在簇間數(shù)據(jù)傳輸上通過多跳算法使數(shù)據(jù)以最優(yōu)路徑傳向匯聚節(jié)點，系統(tǒng)能耗很小,，網(wǎng)絡的生命周期最大化,。

3．1網(wǎng)絡模型

本文中假設傳感器節(jié)點隨機分布在一個長方形形監(jiān)測區(qū)域內(nèi)，并且該傳感器網(wǎng)絡具有以下性質：

1) 網(wǎng)絡中所有傳感器節(jié)點都是同構的,，具有相同的初始能量,，并且能量有限；

2) 傳感器節(jié)點的發(fā)送功率可以進行離散調(diào)節(jié),，可以根據(jù)傳輸距離的遠近來調(diào)節(jié)其發(fā)射功率

3) 匯聚節(jié)點具有較強的計算能力和較大的存儲容量,，且能量無限制，其無線信號可以覆蓋整個傳感器網(wǎng)絡,。

4) 傳感器網(wǎng)絡部署以后,，可以出現(xiàn)部分節(jié)點隨著時間的推移而移動；

5) 傳感器節(jié)點具有數(shù)據(jù)融合功能。

6) 位置上相鄰的節(jié)點采集到的數(shù)據(jù)具有很大的關聯(lián)性,。

3．2能量模型

在無線傳輸中,，信號強度隨著傳輸距離的增加而呈指數(shù)衰減。文獻[3]提出了兩種信道模型：自由空間(free space)模型和多路衰減(multi-path fading)模型,。當發(fā)射器與接收器的距離d小于閾值時,，采用自由空間模型，信號功率呈d²衰減,；否則采用多路衰減模型,，信號功率呈d⁴ 衰減。

3．3成簇策略

在LEACH算法中執(zhí)行過程是周期性進行的,，每一輪包括簇的建立階段和穩(wěn)定的數(shù)據(jù)傳輸階段,。在簇的建立階段，通過選舉使某個節(jié)點成為簇首節(jié)點,，成為簇首的節(jié)點向周圍節(jié)點廣播消息,，其他節(jié)點根據(jù)接收到的廣播消息的強度來選擇它所要加入的簇，并告知相應的簇首,。在本文提出的DTEE算法中,，也是以輪為形式周期進行的，但在簇頭選舉引入了能量因子,，同時第一輪和以后輪的算法過程是不同的,，從第二輪開始在成簇階段可以不用計算公式，相比LEACH及一些改進算法需要計算復雜公式的開銷,，降低了復雜度,，使簇頭選舉能量開銷最低，成簇過程中采用的非均勻成簇方法更是使網(wǎng)絡能量分布更加均衡,。

由于本文采用的是簇內(nèi)單跳,，簇間多跳的數(shù)據(jù)傳輸，因此離Sink節(jié)點遠的簇頭節(jié)點,，數(shù)據(jù)轉發(fā)量越少,，能量消耗的慢；而離Sink節(jié)點越近的簇頭,，其所承擔的數(shù)據(jù)轉發(fā)業(yè)務越多,，消耗能量越大,，所以更容易出現(xiàn)能量耗盡而死亡的情況,。為此，本文拋棄了傳統(tǒng)算法中采用的均勻分簇的方法,，而是采用非均勻成簇的策略,。使離Sink節(jié)點越近的簇，其規(guī)模越小一些，從而這些簇其簇內(nèi)路由及數(shù)據(jù)融合開銷小,，又因為其所承擔的簇頭間數(shù)據(jù)轉發(fā)開銷多,，綜合起來無論離Sink遠還是近的簇頭都將能量相對均衡消耗，網(wǎng)絡生命周期得以最大化,。

非均勻分簇的實現(xiàn)過程是這樣的：首先,，Sink節(jié)點向網(wǎng)絡所在區(qū)域廣播一個NOTICE報文，網(wǎng)絡中所有節(jié)點根據(jù)接收到的此報文能量強度信息確定自己與Sink節(jié)點的距離d(i),。根據(jù)監(jiān)測區(qū)域范圍,、傳感器節(jié)點個數(shù)以及能量自由空間模型確定網(wǎng)絡分層數(shù)n, 然后，本文采用文獻[14]中的均勻分層的方法,，各節(jié)點所在的層號i=d(i)*n/R,，R為監(jiān)測區(qū)域半徑。因為靠近Sink節(jié)點的簇規(guī)模小,，簇內(nèi)節(jié)點少,，也就是所在不同層次的節(jié)點成為簇頭的概率不一樣，各節(jié)點成為簇頭的最佳概率為pi=p/(i*i),。其中p為第一層節(jié)點成為簇頭的概率,。將傳感區(qū)域進行劃分這個動作只出現(xiàn)在第一輪循環(huán)開始的時候，以后的循環(huán)過程不用再進行傳感區(qū)域劃分,。

3．4簇頭選擇

之后開始第一輪的選舉,，各節(jié)點產(chǎn)生一個隨機數(shù) r(n) ，并與T(n)進行比較,，若r(n)小于T(n),，則節(jié)點自選舉成為簇頭。

G為這一輪循環(huán)中未成為簇首的節(jié)點的集合,。

當節(jié)點成為簇頭后,，以適當?shù)陌霃絉C廣播簇頭加入消息，周圍的節(jié)點根據(jù)接收信號強度決定加入哪個簇并發(fā)送一個請求加入消息,。之后簇頭在接收到相關節(jié)點的請求加入消息后,，建立TDMA調(diào)度表并廣播出去。簇內(nèi)節(jié)點在收到此消息后,，在屬于自己的時隙內(nèi)打開無線電模塊開始數(shù)據(jù)傳送,，在其它不屬于自己的時隙內(nèi)關掉通信功能以最大限度節(jié)省能量。在簇內(nèi)節(jié)點向簇頭發(fā)送數(shù)據(jù)報文時,，在其中加入一個本節(jié)點此刻剩余能量的數(shù)據(jù)信息,，供之后算法使用。

第二輪及以后輪的簇頭產(chǎn)生過程中,，首先是上一輪的舊簇頭對收到各節(jié)點報文中含有的各節(jié)點能量信息及自己的剩余能量進行比較,，從中選出剩余能量最大的節(jié)點為新簇頭,，之后舊簇頭以半徑RC發(fā)出new_CH報文，報文中包括報文類型及新簇頭的ID,，當指定的新簇頭收到此報文后發(fā)現(xiàn)ID與之相匹配,，就廣播簇頭加入報文，其余節(jié)點再根據(jù)接收信號強度決定加入哪個簇頭,，之后過程與第一輪相同,。但在實際應用中，網(wǎng)絡節(jié)點有可能意外被移動了,，或者出故障死亡了,，這樣指定的新簇頭就可能不存在了，從而這一簇范圍內(nèi)節(jié)點由于沒收到簇頭加入報文就會整體停止工作,，使網(wǎng)絡出現(xiàn)死區(qū),。考慮此方面,，本文設定舊簇頭節(jié)點在一定的時間閾值內(nèi)若沒有指定的新節(jié)點發(fā)來的簇頭加入報文,，它就確認指定的新節(jié)點被意味移動走了，從而它指定剩余能量第二多的節(jié)點為新節(jié)點,，并發(fā)送新的new_CH報文,。這樣新算法就支持了部分節(jié)點移動或者有新節(jié)點加入的動態(tài)拓撲的網(wǎng)絡。

同時本文設計所有節(jié)點在任一輪循環(huán)中,，從收到簇頭加入報文或new_CH報文開始,，啟動一個計時器Timer，若在最大時限Tmax內(nèi)沒有收到新的簇頭加入報文或new_CH報文,，則啟動從第一輪開始新的簇頭選擇過程,，相對于大多數(shù)算法只支持靜態(tài)網(wǎng)絡，本文的算法支持了小范圍地理位置變動的傳感器網(wǎng)絡,。

3．5數(shù)據(jù)傳輸

在傳感器網(wǎng)絡中,，簇內(nèi)數(shù)據(jù)傳輸為單跳的，在簇首和各成員節(jié)點之間進行,，而對于簇頭到Sink節(jié)點的數(shù)據(jù)傳輸,，LEACH算法及一部分改進算法是采用簇頭到匯聚節(jié)點的單跳傳輸，這種方法使簇頭使用了多徑衰落的通信模型(文獻[3]),，能量消耗很大,，本文采用基于距離因子的多跳傳輸方式。由于采用多跳通信,，能量消耗為自由空間模型,，而且消息在傳送過程中進行了多次數(shù)據(jù)融合，使各級數(shù)據(jù)轉發(fā)中的數(shù)據(jù)量都有所減少,，也減少了通信能耗,。網(wǎng)絡所有節(jié)點都存儲有根據(jù)接收到Sink節(jié)點的信號確定的自己到Sink的距離值，這一距離值在第一輪成簇前就已確定,，我們稱之為距離因子,。當每個簇的簇內(nèi)數(shù)據(jù)融合進行之后，就會開始各簇到Sink的多跳數(shù)據(jù)傳輸,。

首先,，發(fā)送數(shù)據(jù)的簇頭以確定的半徑RD發(fā)送出消息，消息報文中還包含了此簇頭的距離因子,，周圍的簇頭收到消息后,，各簇頭將些距離因子與自己的進行比較，若發(fā)現(xiàn)其距離因子小于報文中的距離因子,，且自己的剩余能量值不低于簇間傳輸所需的最小能量閾值Emin后,，確定自己將此數(shù)據(jù)進行轉發(fā)，將消息報文中的距離因子替換為其距離因子后以半徑RD繼續(xù)轉發(fā),，之后傳輸過程相似,。由于轉發(fā)消息的簇頭的距離因子小，從而其離Sink節(jié)點更近,，這樣消息報文在簇間就以多跳的最優(yōu)路徑傳向了匯聚節(jié)點,。傳輸能量開銷得以最小化。

3 仿真研究

NS2(Network Simulator 2)是著名的用于網(wǎng)絡研究的離散事件仿真工具,，里面包括了大量的用于有線和無線,、本地連接或通過衛(wèi)星連接進行TCP協(xié)議、路由算法,、多播協(xié)議仿真的網(wǎng)絡協(xié)議,、調(diào)度器和工具。NS的核心部分是一個離散事件模擬引擎,。NS中有一個“調(diào)度器”(Scheduler)類,，負責記錄當前時間，調(diào)度網(wǎng)絡事件隊列中的事件,，并提供函數(shù)產(chǎn)生新事件,，指定事件發(fā)生的時間。在仿真過程中,，將執(zhí)行相關算法,，并且將網(wǎng)絡運行的具體情況寫到文件當中，包括數(shù)據(jù)分組的傳遞情況,、節(jié)點的能量狀況等,，這些文件對算法之間進行比較有很大的作用。本文在仿真場景設置方面,，使用了如下場景設置方案：

(1) 仿真區(qū)域大小為(100*100),。

(2) 所有節(jié)點的初始能量相同,。

(3) 傳感器節(jié)點在區(qū)域(100*100)內(nèi)隨機分布。

仿真開始時,，網(wǎng)絡內(nèi)傳感器節(jié)點的分布狀態(tài)如圖1所示,。

仿真結束之后得到了LEACH和DTEE算法生成的相關文件，使用awk程序提取算法生成的相關文件中的關鍵數(shù)據(jù),，然后利用gnuplot工具將這些數(shù)據(jù)顯示于圖表上,，得到兩個算法相比較的曲線圖如圖2所示。

從圖可以看出在仿真過程中,，節(jié)點的能量會隨著時間的推移逐漸減少,，直至節(jié)點能量耗盡而死，所以在各個時段傳感區(qū)內(nèi)仍存有能量的節(jié)點數(shù)是不同的,，圖對兩種算法在不同時段仍然存活的節(jié)點個數(shù)做出了比較,。首先，LEACH算法在第120秒時第一個節(jié)點出現(xiàn)了死亡,，而DTEE是在130多秒時第一個節(jié)點死亡,。從節(jié)點存活數(shù)目圖可以看出，在300秒左右,，LEACH算法的存活節(jié)點數(shù)已經(jīng)為0,，而DTEE算法仍有8個節(jié)點能量并未耗盡，直到320秒左右,，DTEE算法的節(jié)點才全部死亡,，所以DTEE算法中節(jié)點的生命周期比LEACH提高了約6%，可以看出,，DTEE算法由于采用多跳的路由方式,，網(wǎng)絡生命周期得到了一定程度的延長。

本文通過采用引入能量因子的低復雜度簇頭選擇算法降低了網(wǎng)絡通信能耗,，在數(shù)據(jù)傳輸上通過多跳方式進行信息路由,。仿真結果顯示,改進后的DTEE協(xié)議能更好地平衡網(wǎng)絡負載、節(jié)約能量消耗且具有更高的能量使用效率,，對分簇算法的的路由協(xié)議實現(xiàn)了優(yōu)化,。

仿真結束之后得到了LEACH和DTEE算法生成的相關文件，使用awk程序提取算法生成的相關文件中的關鍵數(shù)據(jù),，然后利用gnuplot工具將這些數(shù)據(jù)顯示于圖表上,，得到兩個算法相比較的曲線圖如圖2所示。

從圖可以看出在仿真過程中,，節(jié)點的能量會隨著時間的推移逐漸減少,，直至節(jié)點能量耗盡而死，所以在各個時段傳感區(qū)內(nèi)仍存有能量的節(jié)點數(shù)是不同的,，圖對兩種算法在不同時段仍然存活的節(jié)點個數(shù)做出了比較,。首先,，LEACH算法在第120秒時第一個節(jié)點出現(xiàn)了死亡，而DTEE是在130多秒時第一個節(jié)點死亡,。從節(jié)點存活數(shù)目圖可以看出,，在300秒左右，LEACH算法的存活節(jié)點數(shù)已經(jīng)為0,，而DTEE算法仍有8個節(jié)點能量并未耗盡,，直到320秒左右,，DTEE算法的節(jié)點才全部死亡,，所以DTEE算法中節(jié)點的生命周期比LEACH提高了約6%，可以看出,，DTEE算法由于采用多跳的路由方式,，網(wǎng)絡生命周期得到了一定程度的延長。

本文通過采用引入能量因子的低復雜度簇頭選擇算法降低了網(wǎng)絡通信能耗,，在數(shù)據(jù)傳輸上通過多跳方式進行信息路由,。仿真結果顯示,改進后的DTEE協(xié)議能更好地平衡網(wǎng)絡負載、節(jié)約能量消耗且具有更高的能量使用效率,，對分簇算法的的路由協(xié)議實現(xiàn)了優(yōu)化,。