多傳感器網絡中分簇算法的研究

沈陽理工大學 徐澤民 石振剛

多傳感器網絡拓撲控制目前主要研究的是在網絡保證網絡覆蓋以及具有良好的連通前提下，通過功率控制和節點的選擇達到舍棄節點中一些不必要的無線通信鏈路，生成一個高效可靠的數據轉發網絡拓撲結構。拓撲結構能夠有效的提高路由協議和MAC協議的效率，并為數據融合、目標定位等打下了堅實的基礎，是傳感器網絡研究的一個核心問題之一，同時也是一個熱點問題。

拓撲控制可以分為層次拓撲結構的分層和網絡節點功率控制兩個方面。層次型拓撲控制利用網絡的分簇管理戒指，讓一些節點成為簇節點，由簇節點來對區域內的信息進行采集和穿法，減少其他非骨干網中的節點通信消耗從而達到節省能量的效果。目前已經提出了TopDisc成簇算法，LEACH和HEED等自組織成簇算法。節點功率控制拓撲結構則是調節網絡中各個節點的發射功率，在保證網絡連通的前提下，盡可能的減少節點的發送功率從而來減小網絡能量的消耗。目前提出的有COMPOW等統一功率分配算法，LINT/LILT和LMN/LMA等基于節點度數的算法。

1 LEACH算法

LEACH算法（Low-Energy Adaptive Clustering Hierarchy）算法是由MIT的Heinzelman等人提出的第一個針對無線傳感器網絡分簇拓撲控制的算法。其算法的基本思想是利用循環的方式選舉出網絡中的簇頭節點，將整個網絡的能量消耗均勻的分配到網絡的每個節點中，從而達到降低真個網絡的功耗，提高網絡的壽命長度。

在簇建立過程中，對于簇頭選舉算法的方法如下：每個節點隨機產生一個隨機數并且該隨機數的范圍在0到1之間，若該隨機數小于我們設置的閾值Tn，那么這個節點就成功的當選為出手，并向自己周圍的節點廣播自己當選簇首的消息。Tn的計算公式為：

其中，p表示網絡中預計設計的需要的簇首數量和節點總數的比值，即計算網絡中節點選舉簇首節點的概率；r表示為當前所在的循環次數；G則表示在當前輪次還沒有被選舉為簇首的節點集合。從上式可以看出，在之前被選舉為簇首節點之后的節點并不會繼續進入1/p的循環中從而再次被選舉為簇首，因此余下還沒有當選過簇首的節點再進行競選時的閾值Tn將會變大，從而導致剩下來未成功競選簇首的節點成功當選為簇首的概率變大。

對比平面型網絡拓撲算法，LEACH算法更加容易實現，并初步解決了網絡分層的拓展問題，同時在節約網絡能耗和首個節點能量耗盡時間上有很大的提升。但是該算法仍有很多不足之處：1.簇首的隨機性已經網絡不斷的周期更新簇，會噪聲有大量的成簇消息在網絡中廣播，從而使每個節點可能會接受到很多不必要的信息，這些都會增加羅王的開銷。2.在選舉簇首的時候采用的是隨機選舉的方法，并沒有考慮節點自身所剩余的能量，因此該方法不能保證簇首的質量。3.LEACH采用的是單跳方式，離簇首節點較遠的簇成員可能會由于接受和發送信息產生額外的能量開銷，從而導致這些節點過早的消耗。

2 LEACH算法的改進措施

TEEN路由協議是上述算法的一種改進協議方式。TEEN路由協議的實現理念和LEACH算法基本相同，只不過TEEN協議在LEACH算法的基礎上設置了硬閾值和軟閾值的概念。

TEEN協議中，節點大部分時間將會處于睡眠狀態，當有需要信息的接受或者發送時再進行激活，從而減小了節點的能量消耗。而TEEN算法中對于閾值的設定在整個協議中對于減少能耗具有非凡的意義。硬閾值對采集到的數據進行第一次的篩選，將那些無關緊要的信息進行忽略，減少不必要的通信開銷。軟閾值則是限定數據的變化范圍，即若數據的數值變化量很小的情況下，我們通過設定軟閾值可以判定在當前情況下仍然處于平穩狀態，并不需要向上級匯報，并且這些閾值的設定是由用戶自己設置的，若你想要提高數據的精確性，那么用戶可以通過降低硬閾值，減少軟閾值來實現。不過在得到更精確的數據同時，這樣設定閾值也會相應的提高系統的功耗。

當傳感器網絡中出現節點能量不同的情況時，若仍然使用TEEN的簇頭選舉方法可能會造成節點消耗的能量不一致而使得節點無法一同死亡，那么傳感器網絡的壽命就會大大縮短。為了延長整個傳感器網絡的壽命，我們應該在簇頭選舉的算法上對其進行優化。總所周知，TEEN簇頭選擇的依據是產生隨機數的大小，若這個隨機數超過了閾值，那么這個節點就可以成功當選簇頭，而閾值的公式如下：

其中r代表當前循環次數，P為簇首個數與WSN網絡中節點總數比， G是網絡中未當過簇首的節點集合。

TEEN路由協議的不足：

1)雖然TEEN協議能夠保證各個節點在選舉時擁有相同概率當選簇頭，但是這種情況這適用于各個節點用用相同初始能量的時候，如果傳感器網絡中出現能量異構的情況，則不能使用TEEN協議。

2)簇頭的選擇具有隨機性，可能出現選舉出來的簇頭節點距離太近的情況，從而造成簇的覆蓋重疊，造成不必要的能量浪費。

我們針對不足剩余能量的大小選舉出的簇頭有可能很近，但在很近的距離內有兩個簇頭必定會造成簇的重復覆蓋問題，提出設定最小距離的方法，當一個節點被選為簇頭后對于其后要選的簇頭增加一個條件，即離前面的簇頭要大于一定距離，這個距離閾值的公式如下：

在式（4）中，M為設定的網絡區域的邊長；n總節點數量；Popt為預先設定的簇首比例。另外，當普通節點距離匯聚節點較近時，使其直接將數據發送給匯聚節點，以免造成不必要的浪費。

TEEN算法的不足之處：TEEN是一種應用于時間關鍵敏感的響應性路由協議。在TEEN協議里面，由于簇內的傳感器節點不停的在感應，但是僅在感應值高于硬閾值時才會傳輸，所以能量得到保存。TEEN協議中所有的節點都必須具備與網關通信的能力，僅適用小規模的網絡。

本文研究的是多傳感器協同監視系統的通信，而其中傳感器網絡的組建為其中最為重要的內容之一，因此傳感器網絡的路由搭建方法及通信鏈路中沖突分解方法為本論文的研究重點。本文選用的TEEN分簇路由算法是有LEACH路由算法改進而來的，故論文的主要研究內容為LEACH、TEEN路由算法的原理，進而針對監控系統的環境特點在TEEN算法的基礎上進行改進。