沈陽理工大學(xué) 徐澤民 石振剛

多傳感器網(wǎng)絡(luò)拓?fù)淇刂颇壳爸饕芯康氖窃诰W(wǎng)絡(luò)保證網(wǎng)絡(luò)覆蓋以及具有良好的連通前提下，通過功率控制和節(jié)點的選擇達(dá)到舍棄節(jié)點中一些不必要的無線通信鏈路，生成一個高效可靠的數(shù)據(jù)轉(zhuǎn)發(fā)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。拓?fù)浣Y(jié)構(gòu)能夠有效的提高路由協(xié)議和MAC協(xié)議的效率，并為數(shù)據(jù)融合、目標(biāo)定位等打下了堅實的基礎(chǔ)，是傳感器網(wǎng)絡(luò)研究的一個核心問題之一，同時也是一個熱點問題。

拓?fù)淇刂瓶梢苑譃閷哟瓮負(fù)浣Y(jié)構(gòu)的分層和網(wǎng)絡(luò)節(jié)點功率控制兩個方面。層次型拓?fù)淇刂评镁W(wǎng)絡(luò)的分簇管理戒指，讓一些節(jié)點成為簇節(jié)點，由簇節(jié)點來對區(qū)域內(nèi)的信息進(jìn)行采集和穿法，減少其他非骨干網(wǎng)中的節(jié)點通信消耗從而達(dá)到節(jié)省能量的效果。目前已經(jīng)提出了TopDisc成簇算法，LEACH和HEED等自組織成簇算法。節(jié)點功率控制拓?fù)浣Y(jié)構(gòu)則是調(diào)節(jié)網(wǎng)絡(luò)中各個節(jié)點的發(fā)射功率，在保證網(wǎng)絡(luò)連通的前提下，盡可能的減少節(jié)點的發(fā)送功率從而來減小網(wǎng)絡(luò)能量的消耗。目前提出的有COMPOW等統(tǒng)一功率分配算法，LINT/LILT和LMN/LMA等基于節(jié)點度數(shù)的算法。

1 LEACH算法

LEACH算法（Low-Energy Adaptive Clustering Hierarchy）算法是由MIT的Heinzelman等人提出的第一個針對無線傳感器網(wǎng)絡(luò)分簇拓?fù)淇刂频乃惴?。其算法的基本思想是利用循環(huán)的方式選舉出網(wǎng)絡(luò)中的簇頭節(jié)點，將整個網(wǎng)絡(luò)的能量消耗均勻的分配到網(wǎng)絡(luò)的每個節(jié)點中，從而達(dá)到降低真?zhèn)€網(wǎng)絡(luò)的功耗，提高網(wǎng)絡(luò)的壽命長度。

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

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

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

2 LEACH算法的改進(jìn)措施

TEEN路由協(xié)議是上述算法的一種改進(jìn)協(xié)議方式。TEEN路由協(xié)議的實現(xiàn)理念和LEACH算法基本相同，只不過TEEN協(xié)議在LEACH算法的基礎(chǔ)上設(shè)置了硬閾值和軟閾值的概念。

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

當(dāng)傳感器網(wǎng)絡(luò)中出現(xiàn)節(jié)點能量不同的情況時，若仍然使用TEEN的簇頭選舉方法可能會造成節(jié)點消耗的能量不一致而使得節(jié)點無法一同死亡，那么傳感器網(wǎng)絡(luò)的壽命就會大大縮短。為了延長整個傳感器網(wǎng)絡(luò)的壽命，我們應(yīng)該在簇頭選舉的算法上對其進(jìn)行優(yōu)化?？偹苤?，TEEN簇頭選擇的依據(jù)是產(chǎn)生隨機(jī)數(shù)的大小，若這個隨機(jī)數(shù)超過了閾值，那么這個節(jié)點就可以成功當(dāng)選簇頭，而閾值的公式如下：

其中r代表當(dāng)前循環(huán)次數(shù)，P為簇首個數(shù)與WSN網(wǎng)絡(luò)中節(jié)點總數(shù)比， G是網(wǎng)絡(luò)中未當(dāng)過簇首的節(jié)點集合。

TEEN路由協(xié)議的不足：

1)雖然TEEN協(xié)議能夠保證各個節(jié)點在選舉時擁有相同概率當(dāng)選簇頭，但是這種情況這適用于各個節(jié)點用用相同初始能量的時候，如果傳感器網(wǎng)絡(luò)中出現(xiàn)能量異構(gòu)的情況，則不能使用TEEN協(xié)議。

2)簇頭的選擇具有隨機(jī)性，可能出現(xiàn)選舉出來的簇頭節(jié)點距離太近的情況，從而造成簇的覆蓋重疊，造成不必要的能量浪費(fèi)。

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

在式（4）中，M為設(shè)定的網(wǎng)絡(luò)區(qū)域的邊長；n總節(jié)點數(shù)量；Popt為預(yù)先設(shè)定的簇首比例。另外，當(dāng)普通節(jié)點距離匯聚節(jié)點較近時，使其直接將數(shù)據(jù)發(fā)送給匯聚節(jié)點，以免造成不必要的浪費(fèi)。

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

本文研究的是多傳感器協(xié)同監(jiān)視系統(tǒng)的通信，而其中傳感器網(wǎng)絡(luò)的組建為其中最為重要的內(nèi)容之一，因此傳感器網(wǎng)絡(luò)的路由搭建方法及通信鏈路中沖突分解方法為本論文的研究重點。本文選用的TEEN分簇路由算法是有LEACH路由算法改進(jìn)而來的，故論文的主要研究內(nèi)容為LEACH、TEEN路由算法的原理，進(jìn)而針對監(jiān)控系統(tǒng)的環(huán)境特點在TEEN算法的基礎(chǔ)上進(jìn)行改進(jìn)。