基于權值和代價函數的WSNs 非均勻分簇路由算法*

董國勇，彭 力，吳 凡，聞繼偉

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

0 引 言

無線傳感器網絡(wireless sensor networks，WSNs)節點由于能量受限等特點嚴重影響了其網絡性能，因此，WSNs協議的首要設計目標就是要高效地使用傳感器節點的能量，延長網絡存活時間。

研究人員們陸續提出了分簇路由協議［1～3］。Heinzelman W 等人［1］提出的LEACH 分簇路由協議隨機選舉簇首，收集簇內節點的數據并融合后發送給觀察者來減少能耗。Younis O 等人［4］提出一種混合式的分簇協議HEED，算法根據節點剩余能量來概率性地選取一些候選簇首，然后以簇內部通信代價的高低來競爭產生最終簇首。LEACH-CS［5］以跨區距離的約束來自定義合適的多跳路由方案，通過均勻分簇、多跳路由一定程度上平衡了簇首的能量消耗，但是距離Sink 節點近的簇首會因轉發大量數據而能耗較大，容易導致“熱區”問題。

針對這一問題，李成法等人提出了EEUC［6］非均勻分簇路由算法。依據節點距基站的遠近構建大小不等的簇，離基站越近簇半徑越小，簇內成員越少，為簇首間數據轉發預留能量。然而，算法是隨機地挑選候選簇首，并沒有考慮到節點分布的不均勻性。

文獻［7］提出的WSNs 中基于能量代價的能量優化路由算法在選擇平面路由時利用了節點間能量代價函數和前向區域來選擇下一跳節點。文獻［8］提出的能量均衡的WSNs 非均勻分簇路由協議分簇時采用了定時機制，一定程度上減少了信息交互量。然而，在選擇中繼節點時沒有考慮到節點間的負載均衡。

針對以上算法存在的一些問題，本文提出了一種基于權值和代價函數的WSNs 非均勻分簇路由(uneven clustering routing based on weight and cost function，WCF-UC)算法，算法考慮節點剩余能量與節點密度計算簇首競爭權值。用一個代價函數，綜合考慮簇首剩余能量、簇內成員節點數和位置信息等，決定每個簇首下一跳節點的最優路徑。

1 系統模型

1.1 網絡模型

假設N 個傳感器節點隨機分布在一個M×M 的正方形區域內，且該網絡具有以下性質:1)節點可感知自身剩余能量;2)相鄰節點采集的數據有相似性，可進行數據融合處理;3)鏈路是對稱的，節點可根據RSSI 計算出發送者到自身的近似距離;4)節點可根據需要調整自身發射功率。

1.2 能量消耗模型

本文與文獻［9，10］使用了類似的無線通信模型，發送需要消耗的能量為

接收需要消耗的能量為

其中，Eelec為發送電路和接收電路消耗的能量，εfs，εmp分別為自由空間傳播模型和多路徑衰減傳播模型的能耗，為融合單位比特數據消耗的能量。

2 WCF-UC 算法基本思想

2.1 簇首選擇與簇的建立

算法通過候選簇首競爭方式決定最終簇首，根據節點與基站距離及剩余能量來決定節點競爭半徑。靠近基站的簇首要承擔更多的數據轉發任務，為了節省該簇首的能耗，需要保證節點有較高的能量同時縮小競爭半徑，即根據公式(3)

其中，dmax，dmin分別為節點到Sink 節點的最大和最小距離，d(si，DS)為節點到Sink 節點的距離，R0c 為競爭半徑最大值，c 為0 ～1 可控制取值的參數，Eini，Ei，Emin分別為節點初始能量、剩余能量、設置的最低工作能量。

競爭簇首時，須同時考慮節點剩余能量、充當簇首后能耗及整個區域平均剩余能量。節點剩余能量越大，競爭機會越大;節點越密集，該區域成簇的可能性越大。節點計算收到的各個候選簇首的競爭權值，選擇較大的作為簇首并加入。競爭權值如式(4)

式中 Wn為簇首競爭權值，Ecurrent，Eini分別為該節點剩余能量和初始能量，α 為小于1 的常數，經過實驗，取0.85 時簇首效果最佳;Kc為最佳簇首個數，M 為節點覆蓋區域面積，dtoBS為網絡中心到基站的距離。這里，引入節點密度的概念［11，12］，即節點在某一范圍內的存活鄰居節點數占所有存活節點總數的比重，Qn為節點密度。在每個周期開始，節點對外廣播，收集半徑為RC范圍內的存活節點信息，同時將自身存活情況報告給鄰居節點。這樣可以得到Neighbor(n)alive.RC通過公式(2)獲得。Networkalive可以通過基站在獲得所有節點自身情況時，廣播給網絡內所有節點。

2.2 簇內數據通信

簇內節點交換數據時，簇首將簇內成員節點連成一條數據傳輸鏈，成員節點從傳輸鏈的兩端向簇首傳送數據，因此，簇首只需和鄰近的成員節點各收發一次數據。假設在第a 輪采集過程中，第i 個簇有n 個節點，每個節點每次采集k bit 數據，那么，簇首在這次數據采集過程中接收簇內節點數據和數據融合能量的消耗為

而簇內節點以點對點的方式向簇首傳輸數據時，簇首的能量消耗為

由上式可知，n?3，所以，采用上述算法后，簇首消耗能量將大大減小，可以有效平衡簇首與成員節點的能耗。

2.3 簇間多跳路由

本算法多跳路由設計目標是為了找到一條最優化路徑，以減小簇間數據傳輸時的能耗和避免“熱點”問題。首先，簇首Hi在競爭范圍內廣播一條消息，包括簇內節點數、簇首ID、剩余能量和基站距離。若鄰居簇首到基站的距離較小，那么，簇首Hi計算和鄰居簇首Hj的距離，并且建立一張包含鄰居簇首信息表。

Hi在鄰居簇首集中選擇下一跳節點NHi，該節點在所有的鄰居簇首中具有最小的代價函數。代價函數如下定義

式中 Eavr(Hi)表示簇首Hi鄰居簇首的剩余能量均值，Ecurrent(Hj)為簇首Hj的剩余能量，Nc(Hj)為簇首Hj的成員節點數，Nc_avr(Hi)為簇首Hi鄰居簇首平均節點數，dHi-Hj為Hi到Hj的距離，dHj-BS為Hj到基站的距離，α，β，γ 為加權系數，滿足α+β+γ=1。代價函數第一項是為了選擇剩余能量較大的簇首作為下一跳節點，因為下一跳節點需要轉發數據消耗更多能量，所以，能量因素是首要考慮的;第二項是為了選擇成員節點數量較少的作為下一跳，這樣簇內通信能耗較少，有更多能量用于轉發數據;第三項主要是為了下一跳節點位置的考慮，多跳路由應該盡量選擇最短路徑，使得傳輸能耗最小。如果Hi的下一跳為本身，那么，直接發送數據到基站;否則，將數據發往下一跳節點，所有節點都找到下一跳節點后，簇間多跳路由建立完成。

3 仿真實驗與結果分析

本文在Matlab 平臺下仿真實驗，將500 個節點隨機分布在一個200 m×200 m 區域中，Sink 節點的坐標為(100，250)m。實驗參數如表1 所示。

表1 實驗參數Tab 1 Experimental parameters

算法開始，N×p 個節點成為候選簇廣播N×p 條競選消息。每個候選簇首廣播一條競選簇首成功消息，或廣播一條退出競選消息通知鄰簇首，總N×p 條消息。設共k 個簇首，廣播k 條競選獲勝消息，之后N-k 個普通節點發送N-k 條申請加入消息。總計2N×p+N 條消息。與EEUC算法一樣，本文WCF-UC 也是消息驅動的算法，消息復雜度仍為O(N)。

比較4 種算法的網絡生命周期。如圖1，LEACH 的第一個節點在305 輪死亡，HEED，EEUC，WCF-UC 算法分別為220 輪、480 輪和610 輪，WCF-UC 算法明顯延遲了首個節點失效時間。WCF-UC 算法最后一個節點的死亡輪數是1610 輪，EEUC，HEED，LEACH 算 法 分 別 為1190，1000，790 輪，相對于實驗總輪數(1800 輪)，分別延遲了23.3%，33.9%，45.6%。由此可見，WCF-UC 有效提高了能量的均衡性，延長了網絡生命周期。

圖1 網絡生命周期對比Fig 1 Comparison of network lifetime

簇首能耗占網絡能耗主要部分，因此，須對比4 種協議的簇首能耗之和。實驗中隨機選取10 輪，統計各輪中所有簇首能耗和。如圖2，WCF-UC 和EEUC 算法的簇首能耗最低。因為兩種協議中，簇首采用多跳方式將數據發送至匯聚點，顯著降低了能耗。

圖2 簇首消耗能量之和對比Fig 2 Comparison of sum of cluster heads energy consumption

圖3 對比了4 種算法網絡剩余總能量隨周期的變化情況，LEACH 最先消耗為0。WCF-UC 比LEACH，HEED，EEUC 的能量消耗減少了30.3%，25.2%，10.6%。WCF-UC更有效地節約了能量，因為同時考慮了節點剩余能量、與基站距離及節點分布進行簇首選擇與簇的建立，采用代價函數的多跳路由優化了各簇首間的能量路徑。

4 結束語

本文基于權值和代價函數提出的非均勻分簇路由算法，有效減少了簇首選舉和路由數據轉發能耗。仿真分析表明:WCF-UC 算法網絡存活時間有明顯提高，能有效均衡網絡節點能耗。但是本文沒有考慮簇半徑的優化等問題，有待進一步完善研究。

［1］ Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocols for wireless microsensor networks［C］∥Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2000:3005-3014.

［2］ Heinzelman W，Chandrakasan A，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.IEEE Transactions on Wireless Communications，2002，1(4):660-670.

［3］ Soro S，Heinzelman W.Prolonging the lifetime of wireless sensor networks via unequal clustering［C］∥Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium，2005:236-243.

［4］ Younis O，Fahmy S.HEED:A hybrid，enegry-efficient，distribued clustering approach for Ad Hoc sensor networks［J］.IEEE Transactions on Mobile Computing，2004，3(4):660-669.

［5］ 顧躍躍，白光偉，陶金晶.LEACH-CS:一種自定義的WSNs 跨區多跳路由機制［J］.計算機科學，2011，38(1):78-82.

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

［7］ 許彥芹，陳慶奎.基于SMP 集群的MPI+CUDA 模型的研究與實現［J］.計算機工程與設計，2010，31(15):3408-3412.

［8］ University of Illinois at Urbana-Champaign.Accelerator cluster webpage［EB/OL］.［2013—03—12］.http:∥iacat.illinois.edu/resources/cluster/.

［9］ Ye Mao，Li Chengfa，Chen Guihai，et al.EECS:An energy efficient clustering scheme in wireless sensor networks［C］∥IEEE International Performance Computing and Communications Conference(IPCCC)，2005:535-540.

［10］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks［C］∥Proceedings of the 33rd Annual Hawaii International Conference on System Sciences，2000:1-10.

［11］喬俊峰，劉三陽，曹祥宇.無線傳感器網絡中基于節點密度的簇算法［J］.計算機科學，2009，36(12):46-49.

［12］盧先領，王瑩瑩，王洪斌，等.無線傳感器網絡能量均衡的非均勻分簇算法［J］.計算機科學，2013，40(5):78-81.