距離度量法聚類的無線傳感器網絡路由算法

方旺盛，萬良香，胡中棟

(江西理工大學 信息工程學院，江西 贛州 341000)

0 引 言

無線傳感器網絡(wireless sensor networks，WSNs)[1]一直作為重要的工具，廣泛運用于各類場合中，例如醫療康復[2]、野外戰場環境監測、國家邊境防御裝備等。由于傳感器節點(Node)部署后一般不可移動且難以蓄電，因此如何節省網絡能耗一直是研究的熱點。分簇路由算法[3]與非層次路由算法相比較更節省能耗，所以分簇路由算法為當下研究重點。

文獻[4]基于經典分簇路由LEACH協議算法思想上，提出了以節點與簇頭及節點與基站的距離信息作為簇內節點是否與基站直接通信的判定條件，以節省網絡能耗。文獻[5]提出模糊邏輯算法改進簇頭選取機制及簇群尺寸，以選取更合適的簇頭。文獻[6]基于EEUC協議，引入了能量因素和節點度以改進競爭半徑及閾值的設定，最終提高網絡執行效率。文獻[7]提出了加權值應用于簇首節點閾值，提升簇頭選取質量。文獻[8]提出環狀網絡區域，以劃分區域的方式改進數據傳遞效率，提高網絡生命周期。文獻[9]提出了將無線傳感器網絡劃分為不同大小的圓環，以改善“熱區”問題。文獻[10]提出K-means算法與LEACH協議結合，以減少傳輸能耗。

以上算法大多都是基于LEACH模型進行的改進，雖分簇思想能夠有效提高生命周期，以上文獻也均有考慮到節點能量因素，或綜合考慮能量因素和位置因素，但是對于網絡簇群分布不均問題仍然沒有很好的改善。

因此，本文基于LEACH協議的思想上，為改善網絡簇群分布不均問題，提出DMBC(distance measurement method based clustering algorithm for wireless sensor network)算法，該算法的主要思想是利用節點間距離作為重要指標改進K-means算法，使得簇群分布位置更加均勻，再利用節點的能量特性、位置特性優化每個簇群簇首選擇，最終延長WSNs網絡生命周期。

1 相關模型

1.1 系統模型

本文假定所有節點服從均勻分布且一旦部署后不可移動，其它具體特征如下：①Sink節點有且僅有一個，所有節點位置N(Xi,Yi)已知且不可移動；②每一個節點有相同的初始能量Eo；③部署節點可根據接收到信息的信號強度計算出發送節點到接收節點的距離；④每一個節點有唯一的標識號i,(i=1,2,…,N)；⑤假定各節點均可相互通信，且所有節點均可與Sink節點直接通信；⑥所有節點均具備融合數據的能力。

1.2 無線通信能耗模型

網絡節點在無線通信過程使用的能耗模型采用與文獻[11]相同的無線通信模型，將l比特數據傳輸至距離d處位置時所需要的能耗公式如下

(1)

式中：Eelec表示發射模塊在電路中消耗的能量，傳輸距離存在閾值d0作為能耗分界線，其計算式如下

(2)

當傳輸距離d小于閾值d0時，網絡在傳輸數據的過程中采用自由空間模型；否則網絡在傳輸數據的過程中采用多路徑衰減模型，εfs、εmp分別是兩模型中功率放大所需要消耗的能量。

1.3 數據融合模型

分簇路由協議中，數據融合技術被采用于減少傳輸能耗，即當簇首節點接收到簇內成員傳輸的數據具有相關性時，簇首則將簇內成員發送的信息量壓縮為lbits，此時節點對數據融合所需能耗EDA由式(3)計算所得

EDA(l)=l*5nJ/bit

(3)

2 DMBC路由協議算法

LEACH協議的網絡聚簇效果是和簇頭選取過程共同完成的，但簇頭選取機制考慮因素單一，最終成簇效果不佳，簇群分布不均。因此，本文將網絡聚簇過程和簇頭選取過程分開進行，先將網絡劃分成簇，而后在劃分好的簇內選取合適的簇首節點。聚簇過程是利用改進的K-means算法模型獲得，而簇首選舉機制也加入了能量因素、位置因素,本文先將網絡劃分成簇可以使得網絡保持較好的成簇效果，簇首選取機制的改進也能使得條件更佳的節點成為簇首。

2.1 K-means算法模型

K-means模型可以根據距離相似度將分布在網絡的節點進行聚類，主要的步驟如下：

(1)在網絡中隨機選取K個節點作為初始的中心聚類節點，其它節點選取距離最近的中心聚類節點加入成簇，形成K個初始聚類。

(2)計算簇群的質心節點，每個簇群中與質心節點距離最小的節點成為新的中心聚類節點，而后所有節點加入最近的中心聚類節點產生簇群。

(3)算法迭代步驟(1)、步驟(2)，直到標準測度函數開始收斂，或者是算法迭代多次直到中心聚類節點不再改變，得出聚類結果。

K-means算法比較簡易，但是存在以下因素影響成簇效果：

(1)初始中心聚類節點隨機選取，如果中心聚類節點過于集中會使得簇群過于集中，形成局部最優，導致成簇效果不佳。

(2)通過計算每個簇群的質心，距離質心最近的節點成為新的中心節點，簇群容易受個別“偏僻”節點影響，導致中心節點反而偏離大多數節點。

2.2 初始聚類中心點選取階段優化

2.2.1 最優分簇

本文利用K-means算法思路進行聚類，初始需選取K個中心節點，K值根據文獻[12]確定，其表達式為

(4)

式中：N為區域中節點個數，X為區域邊長，dtoBS為基站至網絡中節點的平均距離，εfs是自由空間信道模型的放大功率所需能耗，εmp是多徑衰落信道模型的放大功率能耗。式中簇群個數K，隨著節點個數N的投放量增加以及區域半徑X擴大而增加，反之則減少；基站至節點距離dtoBS也是改變簇群個數的可變量，基站距離網絡節點越近其簇群個數越多。

2.2.2 中心點選取過程

在K-means路由算法中，隨機性的在網絡中選取K個普通節點，根據質心位置變化迭代聚類，算法實現難度低，但是聚類過程中，容易陷入局部最優。當節點距離分布較近時，在迭代過程中，中心點可能過近甚至出現重合，兩個簇群容易融合為一個簇群；當中心點距離分布遠且在網絡的各個方向分布，則成簇效果會更加合理。因此，針對以上的不足點，本文利用節點間最遠距離作為K個初始中心節點選取的指標[13]。最大距離法的一般公式如下

{dis(d1,dk)*dis(d2,dk)*…*dis(dk-1,dk)≥ dis(d1,di)*dis(d2,di)*…*dis(dk-1,di),di≠d1,d2,…,dk-1}

(5)

式中：dk是網絡中選取出來的中心聚類節點，di是網絡中除已選中的中心聚類節點外的任意節點。

利用上述公式，中心點的優化選取過程如下：

(1)計算N個節點兩兩間的距離dis{i,j}，找出滿足：dis(d1,d2)≥dis(di,dj),(i,j=1,2,…,N)的兩個節點，滿足條件的兩個節點成為初始簇群的中心聚類節點d1、d2。

(2)在剩余的N-2個節點中，找出節點距離條件滿足：{dis(d1,d3)*dis(d2,d3)≥dis(d1,di)*dis(d2,di),(di≠d1,d2)}的節點成為中心聚類節點d3。

(3)在剩余的N-3個節點中，找到節點間距離條件滿足{dis(d1,d4)*dis(d2,d4)*dis(d3,d4)≥dis(d1,di)*dis(d2,di)*dis(d3,di),(di≠d1,d2,d3)}滿足條件的節點成為第4個中心聚類節點d4。

(4)依此類推，剩余K-4個中心節點根據上述方法得出。

2.3 節點距離度量法優化聚類

由于傳統的聚類方法是計算簇群質心獲取的，但是中心點容易受邊界點影響，造成中心點偏移的狀況。因此本文利用了節點距離度量法使得選取的中心點更加貼合簇群，其主要思想：

(1)首先每個節點根據和各中心節點距離，距離條件需滿足：Min{Dis.center(a),(a=1,2,…,K)}，其中Dis.center(a)表示節點和各中心聚類節點距離，節點加入簇群后分配簇群的唯一標識號a，簇群表示為Clustera,(a=1,2,…,K)。

(2)其次在每個Clustera簇群中，各節點計算與該簇內其余節點的距離(聚類節點除外)，其距離表達式為Dis.nodei(a,j),(i,j∈Clustera,i,j≠dk)，同時也計算上一輪中心聚類節點與該簇群節點的距離，表達式為：Dis.ctna(i),(i∈Clustera)。

(3)將Dis.nodei(a,j)、Dis.ctna(i)兩距離進行比較，并利用該距離獲取每個節點的鄰居節點，其鄰居節點獲取表達式如下：Ni.Vic={Dis.nodei(a,j)≥Dis.ctna(i)|i,j∈Clustera},鄰居節點集合中的節點數量越多，表示該節點在簇群中與各節點距離都比較近，因此將集合數目最大的節點更新為新的中心聚類節點，剩余節點重新加入中心節點成簇，直至算法迭代至簇群位置不再更新。

在上述的聚類思想中，聚類指標是節點間距離相似度，聚類中心根據距離相似度將符合標準的節點納入所在簇群，最終聚類出簇大小和簇內成員相似的簇群。

2.4 簇頭選舉

普通節點僅需發送信息傳輸能耗，而簇首節點兼具收發任務，還需將簇內成員信息融合后再發送至Sink節點，因此簇頭節點能量耗損最快，容易出現節點間能量差異大的現象，所以簇頭選擇至關重要。本文對簇頭選舉機制進行了改進，簇頭閾值計算過程引入能量調節因子、質心因子、距離因子3個制約因素，以此改進閾值計算。

2.4.1 能量調節因子

網絡劃分成簇后，因根據距離相似度劃分的簇群，位置分布不同的簇群其大小不一，并且隨著信息傳遞，節點間接收和發送數據是能量不斷消耗的過程，但每個簇群的能耗有所差異，因此能量調節因子定義如下

(6)

2.4.2 質心因子

簇頭選舉過程中，節點的位置要顧慮到大多數節點傳遞信息至簇頭節點時的距離要較小，從而節省傳輸能耗。在此，每個節點定義了質心因子

(7)

2.4.3 距離因子

簇頭不僅僅需要接收簇內節點的信息，還需要將信息融合后傳遞至匯聚節點，所以仍然需要考慮節點至匯聚節點的距離，其距離因子定義為

(8)

式中：distoSink表示網絡所有節點至匯聚節點的平均距離，disi表示節點i至匯聚節點的距離。

根據上述的能量、質心、距離因子，最終得出每個節點的閾值表達式如下

(9)

式中：β1、β2、β3為加權系數，β1表示能量因子加權系數；β2表示質心因子加權系數；β3表示距離因子加權系數。

式(9)結合式(6)可知，節點閾值T(n)與其剩余能量Eres相關，當節點剩余能量越高，閾值越大，成為簇頭可能性越大，降低剩余能量少的節點成為簇頭的可能；結合式(7)中，節點到質心距離distoc與簇內節點至質心距離成反比，即靠近質心的節點成為簇首節點的可能性越大；結合式(8)同理可知，簇內靠近匯聚節點的節點其閾值越高，節點成為簇頭節點后可減少越多傳輸能耗。顯然，算法綜合了候選節點的剩余能量、地理位置優化簇頭選舉機制，從而避免能量低且位置不佳的節點成為簇首節點的可能性。

2.4.4 加權系數變化

在網絡運行全過程中，所有節點不可移動，在網絡初始運行階段所有節點能量差異小，但能量在簇頭選取過程中起重要作用，由此設定初始階段能量加權系數β1=0.5，質心加權系數β2=0.25和距離加權系數β3=0.25。隨著網絡持續運行，全網總能耗不斷下降，節點剩余能量成為選取簇頭的關鍵，因此能量加權系數β1應隨著總能量下降而增大，相對應的質心加權系數β2和距離加權系數β3相應減少，加權系數的增減與以下公式相關

(10)

(1)當Rate(r)=0.2時，即全網總能量下降為初始總能量的20%時，能量加權系數β1增加0.1，對應的加權系數β2、β3均減少0.5，即β1=0.6，β2=0.2，β3=0.2。

(2)當Rate(r)=0.4時，即全網總能量下降為初始總能量的40%時，能量加權系數β1增加0.2，對應的加權系數β2、β3均減少0.1，即β1=0.7，β2=0.15，β3=0.15。

(3)當Rate(r)≥0.6時，即全網總能量下降為初始總能量的60%及以上時，能量加權系數β1增加0.3，對應的加權系數β2、β3均減少0.15，即β1=0.8，β2=0.1，β3=0.1。

根據上述步驟調節加權系數β1、β2、β3的值，可以使得簇頭選取機制更加靈活，在網絡初始運行階段，節點間能量差異小，則重點考慮簇頭節點的位置因素；當網絡總剩余能量下降幅度開始大于初始總能量的20%時，則簇頭節點選取的重要因素逐步放在節點剩余能量上；當網絡總剩余能量僅有初始能量的60%時，此時部分節點能量僅剩初始能量的一半，網絡也已經出現部分死亡節點，為均衡網絡能耗簇頭選舉以剩余能量作為主要的參考因素。

3 實驗仿真

此次實驗使用MATLAB R2017B仿真軟件對LEACH路由協議、LEACH-improved路由協議、DMBC路由協議進行仿真對比。仿真環境為100×100 m的正方形區域，假定區域內節點均勻分布。

表1為實驗仿真所使用的基本參數，為對比協議效果，Sink節點設置于兩個不同位置。

表1 仿真參數的設置

3.1 節點聚類仿真分析

設定在100 m×100 m的網絡中，隨即部署100個節點，對于LEACH路由協議算法中成簇效果的不均勻性以及隨機性導致節點能耗過快問題，本文使用節點間距離相似度而改進的K-means算法聚類成簇，令聚類個數K=5。為避免不必要變量對實驗效果產生影響，則對比算法中簇首個數盡量與本算法相等，設定LEACH協議的節點成為簇首的概率p=0.05，使得兩協議簇頭數目基本保持一致。

3.1.1 初始聚類仿真分析

本文利用最大距離法選取初始中心節點優化的K-means算法，其初始成簇效果如圖1所示。

圖1 網絡初始成簇

根據圖1可以看出，其中心聚類節點的位置在網絡各方向均有分布，每個聚類中心的簇內成員數大小差異不大，以此初始中心節點方向進行中心聚類節點位置更新，不容易造成中心聚類節點距離過近，從而形成局部最優的問題。

3.1.2 聚類結果仿真分析

為更好對比聚簇的實驗效果，LEACH路由協議放入4組在不同輪次中的成簇效果，將其與DMBC協議的聚類結果進行對比。實驗結果如圖2所示。

圖2為隨機選取輪次的LEACH協議成簇效果，圖3為改進過聚類方法的K-means算法最終成簇效果。根據圖2(a)、圖2(b)、圖2(c)、圖2(d)顯示，LEACH協議的簇首節點分布隨機性強但簇群大小差異大，簇頭節點分布位置也不均，從而導致部分節點死亡過快，造成能耗不均的問題。而改進的K-means算法形成的各簇群節點個數差異較小，且簇群位置根據初始成簇方向迭代形成，簇群分布均勻。從圖中的成簇效果也可以看出，中心點位置并沒有因為簇群中的邊界節點而偏移至邊界點方向，在數據傳輸過程中能夠更好均衡網絡能耗。

圖2 LEACH協議成簇實驗結果

圖3 優化K-means算法成簇效果

3.2 網絡生命周期仿真分析

隨著網絡運行時間的增加，區域中的存活節點數反映出網絡生命周期的長短，而生命周期也是表示算法是否改進的重要指標。通過不同算法的存活節點數能夠更加直觀對比生命周期的變化，實驗結果均取自多次實驗的平均值，結果如下：

圖4 死亡節點與輪次關系(Sink位于中心)

圖4與圖5比較了Sink節點不同方位時，各路由算法死亡節點隨輪次變化的差異性。其中，圖4是在Sink節點坐標為(50,50)場景下，死亡節點隨運行時間變化關系。根據多次實驗統計的平均值，得出以下結論：DMBC路由協議第一個死亡節點出現時間相較于LEACH-improved協議延長了百輪以上，并且DMBC路由算法在網絡運行至1500輪之后僅僅只有10個以內的節點死亡，說明優化的K-means聚類算法能夠有效的均衡網絡能耗縮短簇頭節點死亡的時間，而整個網絡所有節點死亡時間相較于其它兩算法也有效的往后延長至2000輪之后。

由于在多數場景中，Sink節點可能遠離于傳感器節點部署區域。因此，圖5是匯聚節點坐標為(100,100)時，各算法死亡節點數的情況。由圖可知，LEACH協議的生命周期最短，而LEACH-improved算法效果會比Sink節點位于中心時效果更優，但是即使不改變DMBC閾值中調節系數的情況下，其死亡節點數仍然相較LEACH-improved協議更少。

圖5 死亡節點與輪次關系(Sink位于邊界)

3.3 剩余能量仿真分析

網絡中衡量節點利用率的重要指標是節點剩余能量，圖6為區域100×100，100個節點，Sink節點位于中心，假定節點的初始總能量為0.5 J，初始總能量為50 J的仿真結果。在相同輪次時，如圖所示，當輪次運行至1000輪時，LEACH協議總體能量所剩不足10 J，而LEACH-improved協議所剩能量還有10 J～15 J，而DMBC路由協議剩余能量還有初始總能量的一半以上。由此可知，本文路由協議均衡網絡能耗的效果最佳，生命周期延長效果最好。

圖6 總剩余能量與輪次關系

4 結束語

本文提出了節點間距離度量法聚類的無線傳感器網絡路由算法——DMBC。結合最優簇頭數，最大距離以及節點間距離度量法的優化的K-means算法，該算法將網絡節點劃分為K個非均勻的簇群進行網絡分區，簇群均勻分布在區域各方向，能夠改善在數據傳輸階段能耗不均的問題；改進聚類方式的同時也改進了簇頭選舉機制。通過實驗仿真對比，相比于LEACH協議和LEACH-improved協議，本文協議改善了簇頭分布不均問題，也解決了網絡運行時簇頭個數太多或太少的問題；在網絡傳輸過程中，LEACH協議及LEACH-improved協議中簇群過大或者是過小的問題均得到改進。因此，在能耗均衡和網絡生命周期仿真結果，DMBC路由協議的效果均有較明顯的提升。