多傳感器網(wǎng)絡(luò)中分簇算法的研究

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

多傳感器網(wǎng)絡(luò)拓?fù)淇刂颇壳爸饕芯康氖窃诰W(wǎng)絡(luò)保證網(wǎng)絡(luò)覆蓋以及具有良好的連通前提下，通過(guò)功率控制和節(jié)點(diǎn)的選擇達(dá)到舍棄節(jié)點(diǎn)中一些不必要的無(wú)線通信鏈路，生成一個(gè)高效可靠的數(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)定位等打下了堅(jiān)實(shí)的基礎(chǔ)，是傳感器網(wǎng)絡(luò)研究的一個(gè)核心問(wèn)題之一，同時(shí)也是一個(gè)熱點(diǎn)問(wèn)題。

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

1 LEACH算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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