摘要：在研究無線傳感器網絡低能耗自適應分簇路由算法LEACH等路由協議基礎上，提出了無線傳感器網絡的動態拓撲能量有效成簇算法：其主要內容包括：1、采用引入能量因子的低復雜度簇頭選擇算法。2、支持部分節點移動的拓撲動態的網絡。3、在數據傳輸上通過多跳方式進行信息路由。理論和仿真結果證明，本算法相對于LEACH算法，在網絡生命周期上得到了提高。
1 引言
無線傳感器網絡（Wireless Sensor Network，WSN）作為下一代的信息獲取技術引起了世界各國的重視，日漸成為國內外學術機構的研究熱點。無線傳感器網絡通常是由大量傳感器節點通過射頻通信形成的一個自組織網絡系統。它通過對被監測對象目標信息的感知，獲取和處理，提供給管理者以有用的信息，可以廣泛地應用于智能家居、醫療衛生、工業控制、農業種植、軍事預警以及防洪救災等特殊場合。但是，WSN與移動Ad Hoc網絡（MANET）是有著很大區別的，它們的通信方式、通信目的和網絡拓撲很不相同，尤其在能量來源方面，WSN是采用電池供電，路由算法對傳感器網絡的存活周期起著重要的影響，所以移動Ad Hoc網絡的路由協議不能完全適應于WSN，我們需要單獨研究適合于無線傳感器網絡的通信協議。
2動態拓撲能量有效成簇算法
針對層次路由協議中存在的各種問題，本文提出了適用于WSN的動態拓撲能量有效成簇算法(DTEE)。此算法引入基于能量因子的低復雜度的簇頭選擇機制，同時通過協議的設計使其支持節點部分離去或有新節點加入的拓撲動態傳感器網絡。在簇間數據傳輸上通過多跳算法使數據以最優路徑傳向匯聚節點，系統能耗很小，網絡的生命周期最大化。
3．1網絡模型
本文中假設傳感器節點隨機分布在一個長方形形監測區域內，并且該傳感器網絡具有以下性質：
1) 網絡中所有傳感器節點都是同構的，具有相同的初始能量，并且能量有限；
2) 傳感器節點的發送功率可以進行離散調節，可以根據傳輸距離的遠近來調節其發射功率
3) 匯聚節點具有較強的計算能力和較大的存儲容量，且能量無限制，其無線信號可以覆蓋整個傳感器網絡。
4) 傳感器網絡部署以后，可以出現部分節點隨著時間的推移而移動；
5) 傳感器節點具有數據融合功能。
6) 位置上相鄰的節點采集到的數據具有很大的關聯性。
3．2能量模型
在無線傳輸中，信號強度隨著傳輸距離的增加而呈指數衰減。文獻[3]提出了兩種信道模型：自由空間(free space)模型和多路衰減(multi-path fading)模型。當發射器與接收器的距離d小于閾值時，采用自由空間模型，信號功率呈d²衰減；否則采用多路衰減模型，信號功率呈d4 衰減。
3．3成簇策略
在LEACH算法中執行過程是周期性進行的，每一輪包括簇的建立階段和穩定的數據傳輸階段。在簇的建立階段，通過選舉使某個節點成為簇首節點，成為簇首的節點向周圍節點廣播消息，其他節點根據接收到的廣播消息的強度來選擇它所要加入的簇，并告知相應的簇首。在本文提出的DTEE算法中，也是以輪為形式周期進行的，但在簇頭選舉引入了能量因子，同時第一輪和以后輪的算法過程是不同的，從第二輪開始在成簇階段可以不用計算公式，相比LEACH及一些改進算法需要計算復雜公式的開銷，降低了復雜度，使簇頭選舉能量開銷最低，成簇過程中采用的非均勻成簇方法更是使網絡能量分布更加均衡。
由于本文采用的是簇內單跳，簇間多跳的數據傳輸，因此離Sink節點遠的簇頭節點，數據轉發量越少，能量消耗的慢；而離Sink節點越近的簇頭，其所承擔的數據轉發業務越多，消耗能量越大，所以更容易出現能量耗盡而死亡的情況。為此，本文拋棄了傳統算法中采用的均勻分簇的方法，而是采用非均勻成簇的策略。使離Sink節點越近的簇，其規模越小一些，從而這些簇其簇內路由及數據融合開銷小，又因為其所承擔的簇頭間數據轉發開銷多，綜合起來無論離Sink遠還是近的簇頭都將能量相對均衡消耗，網絡生命周期得以最大化。
非均勻分簇的實現過程是這樣的：首先，Sink節點向網絡所在區域廣播一個NOTICE報文，網絡中所有節點根據接收到的此報文能量強度信息確定自己與Sink節點的距離d(i)。根據監測區域范圍、傳感器節點個數以及能量自由空間模型確定網絡分層數n, 然后，本文采用文獻[14]中的均勻分層的方法，各節點所在的層號i=d(i)*n/R，R為監測區域半徑。因為靠近Sink節點的簇規模小，簇內節點少，也就是所在不同層次的節點成為簇頭的概率不一樣，各節點成為簇頭的最佳概率為pi=p/(i*i)。其中p為第一層節點成為簇頭的概率。將傳感區域進行劃分這個動作只出現在第一輪循環開始的時候，以后的循環過程不用再進行傳感區域劃分。
3．4簇頭選擇
之后開始第一輪的選舉，各節點產生一個隨機數 r(n) ，并與T(n)進行比較，若r(n)小于T(n)，則節點自選舉成為簇頭。
G為這一輪循環中未成為簇首的節點的集合。
當節點成為簇頭后，以適當的半徑RC廣播簇頭加入消息，周圍的節點根據接收信號強度決定加入哪個簇并發送一個請求加入消息。之后簇頭在接收到相關節點的請求加入消息后，建立TDMA調度表并廣播出去。簇內節點在收到此消息后，在屬于自己的時隙內打開無線電模塊開始數據傳送，在其它不屬于自己的時隙內關掉通信功能以最大限度節省能量。在簇內節點向簇頭發送數據報文時，在其中加入一個本節點此刻剩余能量的數據信息，供之后算法使用。
第二輪及以后輪的簇頭產生過程中，首先是上一輪的舊簇頭對收到各節點報文中含有的各節點能量信息及自己的剩余能量進行比較，從中選出剩余能量最大的節點為新簇頭，之后舊簇頭以半徑RC發出new_CH報文，報文中包括報文類型及新簇頭的ID，當指定的新簇頭收到此報文后發現ID與之相匹配，就廣播簇頭加入報文，其余節點再根據接收信號強度決定加入哪個簇頭，之后過程與第一輪相同。但在實際應用中，網絡節點有可能意外被移動了，或者出故障死亡了，這樣指定的新簇頭就可能不存在了，從而這一簇范圍內節點由于沒收到簇頭加入報文就會整體停止工作，使網絡出現死區。考慮此方面，本文設定舊簇頭節點在一定的時間閾值內若沒有指定的新節點發來的簇頭加入報文，它就確認指定的新節點被意味移動走了，從而它指定剩余能量第二多的節點為新節點，并發送新的new_CH報文。這樣新算法就支持了部分節點移動或者有新節點加入的動態拓撲的網絡。
同時本文設計所有節點在任一輪循環中，從收到簇頭加入報文或new_CH報文開始，啟動一個計時器Timer，若在最大時限Tmax內沒有收到新的簇頭加入報文或new_CH報文，則啟動從第一輪開始新的簇頭選擇過程，相對于大多數算法只支持靜態網絡，本文的算法支持了小范圍地理位置變動的傳感器網絡。
3．5數據傳輸
在傳感器網絡中，簇內數據傳輸為單跳的，在簇首和各成員節點之間進行，而對于簇頭到Sink節點的數據傳輸，LEACH算法及一部分改進算法是采用簇頭到匯聚節點的單跳傳輸，這種方法使簇頭使用了多徑衰落的通信模型(文獻[3])，能量消耗很大，本文采用基于距離因子的多跳傳輸方式。由于采用多跳通信，能量消耗為自由空間模型，而且消息在傳送過程中進行了多次數據融合，使各級數據轉發中的數據量都有所減少，也減少了通信能耗。網絡所有節點都存儲有根據接收到Sink節點的信號確定的自己到Sink的距離值，這一距離值在第一輪成簇前就已確定，我們稱之為距離因子。當每個簇的簇內數據融合進行之后，就會開始各簇到Sink的多跳數據傳輸。
首先，發送數據的簇頭以確定的半徑RD發送出消息，消息報文中還包含了此簇頭的距離因子，周圍的簇頭收到消息后，各簇頭將些距離因子與自己的進行比較，若發現其距離因子小于報文中的距離因子，且自己的剩余能量值不低于簇間傳輸所需的最小能量閾值Emin后，確定自己將此數據進行轉發，將消息報文中的距離因子替換為其距離因子后以半徑RD繼續轉發，之后傳輸過程相似。由于轉發消息的簇頭的距離因子小，從而其離Sink節點更近，這樣消息報文在簇間就以多跳的最優路徑傳向了匯聚節點。傳輸能量開銷得以最小化。
3 仿真研究
NS2(Network Simulator 2)是著名的用于網絡研究的離散事件仿真工具，里面包括了大量的用于有線和無線、本地連接或通過衛星連接進行TCP協議、路由算法、多播協議仿真的網絡協議、調度器和工具。NS的核心部分是一個離散事件模擬引擎。NS中有一個“調度器”(Scheduler)類，負責記錄當前時間，調度網絡事件隊列中的事件，并提供函數產生新事件，指定事件發生的時間。在仿真過程中，將執行相關算法，并且將網絡運行的具體情況寫到文件當中，包括數據分組的傳遞情況、節點的能量狀況等，這些文件對算法之間進行比較有很大的作用。本文在仿真場景設置方面，使用了如下場景設置方案：
(1) 仿真區域大小為(100*100)。
(2) 所有節點的初始能量相同。
(3) 傳感器節點在區域(100*100)內隨機分布。
仿真開始時，網絡內傳感器節點的分布狀態如圖1所示。
仿真結束之后得到了LEACH和DTEE算法生成的相關文件，使用awk程序提取算法生成的相關文件中的關鍵數據，然后利用gnuplot工具將這些數據顯示于圖表上，得到兩個算法相比較的曲線圖如圖2所示。
從圖可以看出在仿真過程中，節點的能量會隨著時間的推移逐漸減少，直至節點能量耗盡而死，所以在各個時段傳感區內仍存有能量的節點數是不同的，圖對兩種算法在不同時段仍然存活的節點個數做出了比較。首先，LEACH算法在第120秒時第一個節點出現了死亡，而DTEE是在130多秒時第一個節點死亡。從節點存活數目圖可以看出，在300秒左右，LEACH算法的存活節點數已經為0，而DTEE算法仍有8個節點能量并未耗盡，直到320秒左右，DTEE算法的節點才全部死亡，所以DTEE算法中節點的生命周期比LEACH提高了約6%，可以看出，DTEE算法由于采用多跳的路由方式，網絡生命周期得到了一定程度的延長。
本文通過采用引入能量因子的低復雜度簇頭選擇算法降低了網絡通信能耗，在數據傳輸上通過多跳方式進行信息路由。仿真結果顯示,改進后的DTEE協議能更好地平衡網絡負載、節約能量消耗且具有更高的能量使用效率，對分簇算法的的路由協議實現了優化。
仿真結束之后得到了LEACH和DTEE算法生成的相關文件，使用awk程序提取算法生成的相關文件中的關鍵數據，然后利用gnuplot工具將這些數據顯示于圖表上，得到兩個算法相比較的曲線圖如圖2所示。
從圖可以看出在仿真過程中，節點的能量會隨著時間的推移逐漸減少，直至節點能量耗盡而死，所以在各個時段傳感區內仍存有能量的節點數是不同的，圖對兩種算法在不同時段仍然存活的節點個數做出了比較。首先，LEACH算法在第120秒時第一個節點出現了死亡，而DTEE是在130多秒時第一個節點死亡。從節點存活數目圖可以看出，在300秒左右，LEACH算法的存活節點數已經為0，而DTEE算法仍有8個節點能量并未耗盡，直到320秒左右，DTEE算法的節點才全部死亡，所以DTEE算法中節點的生命周期比LEACH提高了約6%，可以看出，DTEE算法由于采用多跳的路由方式，網絡生命周期得到了一定程度的延長。
本文通過采用引入能量因子的低復雜度簇頭選擇算法降低了網絡通信能耗，在數據傳輸上通過多跳方式進行信息路由。仿真結果顯示,改進后的DTEE協議能更好地平衡網絡負載、節約能量消耗且具有更高的能量使用效率，對分簇算法的的路由協議實現了優化。