低冗余度WSN 非均勻分簇算法應用研究

陳 樹，韓 進，蔣 偉

(江南大學物聯網工程學院，江蘇 無錫 214122)

1 概述

無線傳感器網絡理論研究模型大都基于高節點冗余度的網絡，但在很多應用場景中，部署高冗余度的無線傳感網絡是不現實的。通常用于工業生產的無線傳感網絡節點價格比較高，不會有大量的冗余節點，這就造成了整個網絡節點的低冗余度。這種低冗余度要求整個系統數據傳輸的能耗均勻分布和傳感節點之間的能耗均勻，避免出現節點早衰現象。作為傳感器網絡數據傳輸路徑選擇的路由策略對均衡節點能耗負載、節省通信能量、延長網絡生存時間起決定作用［1］。但常規的路由協議不能簡單直接地應用到低冗余度的網絡中，必須選擇基本的路由算法并進行適當地修改，以符合實際應用場景。通過對現有無線傳感器網絡路由算法的研究，發現分簇路由協議技術能顯著降低數據延遲，提高能量利用率，有效延長網絡生命周期，相比之下具有更好的適用性。目前，研究者已就如何延長無線傳感器網絡生存時間提出多種分簇路由協議。例如，Heinzelman 等人提出了經典的低功耗自適應分簇協議LEACH［2］，設計思想是隨機按“輪”的形式以一定概率周期性的循環選擇簇首節點，即讓節點輪流擔任簇首，從而將網絡中的能量負載平均分配到每個傳感器節點，延長網絡生存周期。但此算法是隨機選取簇頭，難以保證每輪的簇頭數目一致和簇頭在網絡中均勻分布，無法確保整個網絡能耗的均衡性，可能會出現節點成堆死亡的情況。之后Heinzelman 等人又提出了LEACH-C 算法［3］，該算法雖然提高了成簇質量，采用多跳的簇間路由機制，但是其網絡流量、時間延遲及信號干擾的概率會增加，成簇開銷也增大，存在嚴重“熱區”問題。文獻［4］提出了一種EECS 的非均勻分簇算法，該算法通過選舉得到簇首節點，剩余節點根據通信代價公式，選擇加入到代價最小的簇中，從而構造大小不同的簇以均衡簇首負載，然后簇首以單跳的方式與基站通信。之后文獻［5］又提出了一種新的非均勻分簇路由算法EEUC，構造不同規模的簇來改善多跳路由的“熱區”問題。但上述2 種算法都存在簇首數目隨機和簇間傳輸方式單一的問題，造成簇首能耗不易控制。

對于低冗余度網絡，任何節點的過早死亡、能耗不均和不穩定因素都會給工業生產過程造成較大影響。由于上述各種分簇協議均存在一些問題，因此不能直接應用到低冗余度的網絡。針對該問題，本文提出一種基于粒子群優化(Particle Swarm Optimization，PSO)算法和最短路由樹的分簇路由算法。該算法在EEUC 協議基礎上引入粒子群算法優化非均勻分簇過程，并將所有簇首節點以基站為根構成最短路由樹，樹內節點通過多跳路由將數據傳輸給基站。

2 網絡模型

2.1 前提假設

假設無線傳感器網絡的特性如下:

(1)節點均勻部署在方形網絡中，且位置不再變動;基站位于網絡空間外側，其能量和計算能力不受限制，傳輸范圍覆蓋整個網絡。

(2)簇首節點和普通節點的ID 號均唯一，且簇首節點具有數據融合和轉發能力。

(3)節點位置坐標已事先測得，發射功率可根據接收節點的距離自動調節。

(4)每個普通節點最大通信半徑設為Rmax，簇首節點的競爭半徑設為Rc。

(5)算法無需周期性地從普通節點中選取簇首節點，由控制中心根據選簇機制一次性選取固定數目的簇首節點，最后可由工作人員根據選好的最優簇首組合的位置部署簇首節點。

2.2 能量模型

無線傳感器網絡的能耗大部分來自通信，通信所消耗的能量比感知和計算所消耗的能量要大得多，本文不考慮節點運算和存儲所消耗的能量，參考文獻［2］得到本文算法的無線通信能耗模型，發送和接收l 字節數據的消耗能量分別為:

其中，l 表示收發的字節數;d 表示通信距離;在文獻［5］中若通信距離小于閾值d0，功率放大損耗采用自由空間模型;若通信距離不小于閾值d0時，采用多路徑衰減模型;Eelec表示收發電路的基本功耗系數;Efs，Eamp表示功率放大電路的功耗系數。

3 本文算法

基于粒子群和最短路由樹的非均勻分簇路由算法采用集中式控制策略［6］，簇首選舉和最短路由樹建立過程的能量開銷都由能量不受限制的基站承擔執行，從而減少網絡傳感節點的能耗，較好地適應了低冗余度無線傳感網絡。整個算法過程分為3 個階段:粒子群優化的非均勻分簇階段;基站和簇首節點之間建立最短路由樹階段;數據傳輸和路由更新階段。

3.1 非均勻分簇

非均勻分簇階段分為簇首選取和普通節點加入簇，而簇首選取引入粒子群優化算法完成非均勻分簇。PSO 算法具有收斂速度快、算法簡單和易于實現等優點，在求解單目標優化問題上是一種有效的方法［7］，將其引入簇首選取階段可以減少非均勻分簇算法的復雜度。

首先，為達到非均勻分簇效果，分簇時引入大小不同的競爭半徑，如式(3)所示，競爭半徑是根據簇首到基站距離計算得到，使得遠離基站的簇首數量少，成簇規模大;靠近基站的簇首數量多，成簇規模小［8］。

其中，λ 屬于［0，1］的常數;Dmax和Dmin分別表示簇首節點和基站之間距離的最大值和最小值;d(Cm，BS)表示簇首節點Cm到基站的距離;R0為競爭半徑最大值。

其次，在PSO 算法優化分簇過程時，適應值函數設定是否理想直接決定最終選取的簇首優劣。根據本文研究背景，算法將簇內通信代價和簇首位置作為適應值函數的影響因子。因此，PSO 算法的適應值函數可構造為:

其中，f1(pi)為成簇緊湊性評價因子，等于普通節點至其簇首的最大平均歐式距離;Cpi，m表示粒子pi中簇首Cm所屬普通節點數目;f2(pi)為所有簇首包含節點數之和與節點總數比值的倒數，表示簇首節點覆蓋范圍的大小;α 和β 屬于［0，1］且α+β=1，通過調節f1(pi)和f2(pi)在適應值函數中所占比例，從而優化簇分布及簇選擇。根據適應值函數的定義，本文PSO 優化分簇過程可以簡單描述為:在假定的網絡搜索空間中，找到一個最優簇首組合(M 個簇首)，使得適應函數值最小。PSO 優化分簇算法基本步驟如下:

(1)初始化Q 個粒子，每個粒子包含M 個簇首節點，代表一種可能的分簇方式。

(2)初始化每個粒子pi:

1)初始化粒子pi的位置，即從［0，L］內隨機產生一個實數作為每個粒子位置向量中每一維的值。

2)初始化粒子pi的速度，即從［-V，V］內隨機產生一個實數作為每個粒子速度向量中每一維的值。

(3)計算每個粒子的適應函數值:

1)對于每個普通節點ci(i=1，2，…，N)，計算其到所有簇首節點Cm(m=1，2，…，M)的距離d(ci，CHpi，m);根據式(3)計算每個簇首的競爭半徑，并計算其競爭半徑范圍內所包含的的節點數Cpi，m。

2)運用式(4)～式(6)計算粒子的適應函數值fit(pi)。

(4)確定每個粒子的局部最優解和種群最優解。

(5)根據文獻［7］中的粒子群算法基本公式更新每個粒子的位置和速度。

(6)重復步驟(3)～步驟(5)，直至達到最大迭代次數。

最后，當基站從上位機得到最優簇首組合及簇成員信息后，廣播非均勻分簇結果給每個節點，普通節點加入簇，組建網絡的分簇階段基本完成。

3.2 最短路由樹的建立

本文采用Dijkstra 算法建立基站和簇首之間的最短路由樹。Dijkstra 算法是解決關于帶權有向圖的最短路徑問題的一種貪心算法，它要逐個地找出從源節點出發到所有其他節點的最短路徑，算法的本質特征是能夠確定路徑順序，按照加權長度順序首先找出最短路徑，直至最后找出從源節點到所有節點的最短路徑［9］。

為了均衡簇間多跳傳輸的能耗，將節點的傳輸能耗、剩余能量和成簇規模作為路由樹邊的權值公式影響因子，公式如式(7)所示。

其中，W(i，j)表示圖中連接相鄰簇首節點i 和節點j的邊的權值;Etx(l，d)表示節點j 向節點i 發送l 比特數據所消耗的能量，其大小可根據式(1)計算得到;Re(i)，Re(j)分別表示節點i 和節點j 的剩余能量;Cn(i)和N 分別表示節點i 的簇成員數和網絡普通節點總數;ε 和θ 是屬于［0，1］的常數;ω 為公式歸一化常數。

根據前提假設，網絡中簇首一旦選定，其拓撲結構不再改變，因此，在每輪采集周期中，所有簇首節點間的拓撲結構可用一個帶權值的有向連通圖G=(V，E)表示，其中，V 表示網絡中所有的簇首節點(包括基站)的集合;E 表示圖中所有邊的集合。本文為了便于簇間多跳路徑的建立，根據簇首到基站的距離將所有簇首節點分屬不同的層次，處于n 層的簇首和基站通信需要n -1 層的簇首節點進行轉發，且簇首節點不對來自上一層的簇首數據包進行融合處理，只是轉發給自己的下一跳簇首，這樣可以形成較好的樹型結構［10］。假設源頂點到某個節點v的通信代價為D(v)，表示從源頂點到節點v 所經過的整條鏈路權值之和。則利用Dijkstra 算法構造最短路由樹的步驟如下:

(1)初始化。設網絡頂點集合為U，選擇基站為源頂點S0，并加入到集合U 中，此時U={S0}，對于所有不在U 中的節點v，有如下公式:

其中，W(s0，v)可根據式(7)計算得到;∞可以用一很大的數值代替，只要比樹中任何邊的權值大就行。

(2)從V-U 的集合中找到節點u，且其D(u)的值最小，然后將其加入到U 中。接著對所有其他V-U中的節點v，用{D(v)，D(u)+W(u，v)}中的較小的值去更新原有的D(v)值，即:

(3)重復步驟(2)，直至所有簇首節點都在U 中為止，即U=V。

最終建立完成以基站為根的最短路由樹。基站則根據最短路由樹計算出每個簇首節點的路由表信息并將其廣播給所有簇首節點，然后簇首節點可以按照路由表，將數據發送給各自的下一跳節點，最終將數據轉發給基站。網絡模型如圖1 所示。

圖1 最短路由樹網絡模型

3.3 數據傳輸和路由更新

數據傳輸主要分為簇內傳輸和簇間傳輸2 個階段。簇內傳輸時，節點按照時分多址(Time Division Multiple Address，TDMA)的方式將檢測數據傳輸給簇首節點;簇間傳輸時，簇首節點根據已經建立好的最短路由樹將融合好的數據傳輸給自己的父節點，然后經過轉發，最終到達基站［11］。

簇間多跳傳輸階段，必須考慮某一條路徑中轉發節點能耗過快而提早死亡的情況。因此，在每一輪傳輸結束后，基站重新計算路由樹中各邊的權值，當某條邊的權值高于設定的閾值時，則對最短路由樹進行動態更新。參考文獻［12］得到本文算法動態路由更新的基本過程如下:

(1)網絡中某條邊的權值過高導致網絡路徑被割斷，原來的最短路由樹被分為了2 棵獨立的樹，此時需要變更路徑。

(2)將原來最短路由樹中到源頂點的最短路徑沒有改變的樹中節點構成集合TN1，而被切斷的樹中的節點構成集合TN2。

(3)將集合TN2 中的節點再按照上一節中Dijkstra 算法的基本思路逐個地加入到集合TN1 中，同時將對應節點從TN2 中刪除，直到集合TN2為空。

最后便得到了動態更新后的最短路由樹。利用此方法不需要重新計算生成整個網絡的最短路由樹，不但節省了計算時間，而且還避免了不必要的網絡能耗。

4 實驗結果及分析

為評估本文算法在低冗余度的無線傳感器網絡中的可用性和有效性，筆者引入EECS 和EEUC 算法與之比較。仿真環境和具體參數如下:在100 ×100的方形區域均勻部署200 個傳感器節點;控制包大小200 bit;數據包大小4 000 bit;節點初始能量總和100 J，簇首數目M=10，基站坐標(50，125);λ=0.5，R0=70 m;ε=0.3，θ=0.5，ω=1 000。PSO 參數設置［7］:種群規模Q=50;學習因子c1=c2=2;慣性因子w=0.8;r1，r2 隨機給出;α=0.7，β=0.3;最大迭代次數為100。

將本文算法和EECS、EEUC 算法進行比較后可知，EECS 算法為均衡節點能耗，將節點分成大小不同的簇，但是簇首與基站的通信采用簡單的單跳機制，容易過快地消耗簇首能量，而導致整個網絡的生存周期變短。EEUC 算法則在非均勻分簇的基礎上，簇間采用多跳路由方式傳輸和轉發數據，所以消耗的能量更少，一定程度上延長了網絡生命周期。不同于上述2 種算法，本文算法不僅在分簇階段引入粒子群算法優化選簇過程，而且在數據傳輸和轉發階段，采用多跳路由并通過建立最短路由樹的形式尋求最優路徑，以及動態路由更新機制，使得能量消耗比其他算法要慢的多，顯著地延長了網絡有效生命時間。

EEUS、EECS 和本文算法存活節點數隨著網絡生命時間的變化情況如圖2 所示。

圖2 網絡節點存活數量比較

可以看出，在相對有效的網絡生命時間里(存活節點數大于100)，EECS 和EEUC 算法分別在243 輪和345 輪時開始出現第1 個節點的死亡，而本文算法將第1 個節點的死亡時間推遲到649 輪，這是因為本文算法相比于其他2 種算法有如下優勢:

(1)為了均衡網絡能耗，在選擇簇首時，利用PSO 算法選取最優簇首組合分布信息，而EECS 和EEUC 的簇首數目都是隨機的，很容易造成能耗不均的問題。

(2)通過在基站與簇首之間建立最短路由樹的形式尋找最優路徑以及采用動態更新路由機制，減少了多跳傳輸的能耗，有效地延長了網絡生命周期。

(3)根據低冗余度WSN 的特點，本文算法在WSN 初始能量相同的情況下，采用簇首和普通節點能量差異化分配機制，使得簇首節點的初始能量略高于普通節點的初始能量，這樣可以延長固定簇首生命時間，保證網絡有效運行。

EEUS、EECS 和本文算法前100 輪采集周期各個協議簇首平均能耗變化如圖3 所示。可以看出，EECS 算法的簇首平均能耗處于偏高的位置振蕩，原因是EECS 算法中所有簇首采用單跳方式與基站通信，比EEUC 算法和本文算法的簇間多跳傳輸方式要消耗更多的能量。而EECS 和EEUC 算法簇首平均能耗出現不穩定的振蕩現象，則是由于2 種算法在選擇簇首時數目是隨機的，導致簇首多時，能耗低;反之，能耗高的問題，造成節點能耗不均衡。所以，本文算法所采用的選簇方式和簇間多跳路徑選擇機制使得簇首平均能耗處于低位穩定的狀態，能夠較好地均衡節點能耗，延長網絡壽命。

圖3 網絡簇首平均能耗比較

5 結束語

本文針對低冗余度的無線傳感器網絡，提出一種基于粒子群和最短路由樹的非均勻分簇路由算法，該算法具有如下特點:(1)利用PSO 算法優化分簇過程，一次性選擇固定數目簇首，不僅滿足實際網絡簡單穩定的要求，還降低了算法復雜度，提高了分簇效率;(2)通過建立最短路由樹的方式進行數據的傳輸和轉發以及動態地更新最短路由樹，能夠很好地均衡網絡節點能耗;(3)用來檢測參數的普通節點不擔任簇首，節點能耗更均衡、壽命更長，保證了檢測質量。仿真結果表明，本文算法在應用到節點冗余度低的無線傳感器網絡中時，能有效降低節點死亡速度，延長網絡有效生存時間，為進一步應用到工業生產中的低冗余度無線傳感器網絡提供理論依據。

［1］沈 波，張世永，鐘亦平.無線傳感器網絡分簇路由協議［J］.軟件學報，2006，17(7):1588-1600.

［2］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy Efficient Communication Protocol for Wireless Sensor Networks ［C］//Proceedings of the 33rd Hawaii International Conference on System Sciences.Hawaii，USA:［s.n.］，2000:3005-3014.

［3］Heinzelman W.An Application-specific Protocol Architecture for Wireless MicroSensor Networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

［4］Ye Mao，Li Chengfa，Chen Guihai，et al.EECS:An Energy Efficient Cluster Scheme in Wireless Senor Networks［C］//Proceedings of the 24th IEEE Inter-national Conference on Performance，Computing，and Communications.Phoenix，USA:IEEE Press，2005:535-540.

［5］李成法，陳貴海，吳 杰，等.一種基于非均勻分簇的無線傳感器網絡路由協議［J］.計算機學報，2007，30(1):27-36.

［6］蔣暢江，石為人，唐賢倫，等.能量均衡的無線傳感器網絡非均勻分簇路由協議［J］.軟件學報，2012，23(5):1223-1231.

［7］蘇 兵，黃冠發.基于粒子群優化的WSN 非均勻分簇路由算法［J］.計算機應用，2011，31(9):2340-2343.

［8］李 鑒，石 馨，劉賀平.煤礦巷道無線傳感器網絡非均勻分簇數據傳送機制［J］.中國地質大學學報，2013，38(1):196-200.

［9］Conmen T H，Leiserson C E，Rivest R L，et al.算法導論［M］.2 版.潘金貴，顧鐵成，李成法，等，譯.北京:機械工業出版社，2006.

［10］尚鳳軍，任東海.無線傳感器網絡中分布式多跳路由算法研究［J］.傳感技術學報，2012，25(4):530-534.

［11］張明才，薛安榮，王 偉.基于最小生成樹的非均勻分簇路由算法［J］.計算機應用，2012，32(3):787-790.

［12］Narvaez P，Siu K Y，Tzeng H Y.New Dynamic Algorithms for Shortest Path Tree Computation［J］.IEEE/ACM Transactions on Networking，2000，8(9):734-746.