基于加權(quán)優(yōu)化樹(shù)的WSN分簇路由算法

劉一玨， 王 軍

(沈陽(yáng)化工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 遼寧 沈陽(yáng) 110142)

隨著傳感器技術(shù)、物聯(lián)網(wǎng)等技術(shù)的發(fā)展，低成本、低能耗、多功能的無(wú)線傳感器技術(shù)得到了快速的發(fā)展. 無(wú)線傳感器網(wǎng)絡(luò)(wireless sensor networks,WSN)因其成本低、部署方便、安全系數(shù)高等特點(diǎn)，被廣泛應(yīng)用于各個(gè)領(lǐng)域，也成為目前研究的重點(diǎn)[1].由于無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)能量受限，而且不能隨時(shí)補(bǔ)充，因此，優(yōu)化路由算法，使其在網(wǎng)絡(luò)的構(gòu)建和路由選擇過(guò)程中消耗更少的能量是路由算法設(shè)計(jì)時(shí)需要考慮的首要問(wèn)題.

為了解決無(wú)線傳感器網(wǎng)絡(luò)的能耗問(wèn)題，研究人員提出很多路由算法，如低功耗自適應(yīng)集簇分層算法[2](low energy adaptive clustering hierarchy,LEACH)、傳感器信息系統(tǒng)高效聚類(lèi)算法[3](power efficient gathering in sensor information system,PEGASIS)、能量有效的非均勻成簇算法[4](energy-efficient une-ven clustering，EEUC)等.LEACH算法是經(jīng)典的分簇算法，采用依次當(dāng)選簇頭與數(shù)據(jù)融合[5]的方式來(lái)降低節(jié)點(diǎn)的能量消耗，增大了網(wǎng)絡(luò)的生存時(shí)間，但是簇頭的選取是根據(jù)概率隨機(jī)進(jìn)行選擇，沒(méi)有考慮節(jié)點(diǎn)間的距離和節(jié)點(diǎn)的剩余能量，所以，所選擇的簇頭分布不均衡[6]并且不合理；PEGASIS算法采用貪心算法，在網(wǎng)絡(luò)中把節(jié)點(diǎn)成鏈，節(jié)點(diǎn)只與最近的節(jié)點(diǎn)進(jìn)行通信，最后選取一個(gè)鏈頭節(jié)點(diǎn)與基站通信，減少了節(jié)點(diǎn)間數(shù)據(jù)傳輸?shù)南?，但是形成的鏈過(guò)長(zhǎng)，導(dǎo)致傳輸時(shí)間延遲，不適用于實(shí)時(shí)的場(chǎng)所；EEUC算法采用非均勻分簇的思想，均衡了網(wǎng)絡(luò)中的能量消耗，增長(zhǎng)了網(wǎng)絡(luò)的生存時(shí)間，但根據(jù)概率和門(mén)限選取簇頭，不能保證簇首的高效性.

上述算法都在不同的方面進(jìn)行了優(yōu)化，但都沒(méi)有對(duì)簇內(nèi)的通信代價(jià)進(jìn)行優(yōu)化，沒(méi)有將能耗和時(shí)延同時(shí)考慮.針對(duì)上述問(wèn)題，本文以延長(zhǎng)網(wǎng)絡(luò)生存時(shí)間和平衡網(wǎng)絡(luò)能耗為主要目的，提出節(jié)點(diǎn)間數(shù)據(jù)傳輸代價(jià)，對(duì)樹(shù)型結(jié)構(gòu)進(jìn)行加權(quán)優(yōu)化并將其應(yīng)用于分簇路由算法中，以達(dá)到減少節(jié)點(diǎn)能耗、增長(zhǎng)網(wǎng)絡(luò)生存時(shí)間的目的.

1 相關(guān)工作

1.1 網(wǎng)絡(luò)模型

為了更好地進(jìn)行研究，對(duì)網(wǎng)絡(luò)模型[7]做如下規(guī)定：

(1) 節(jié)點(diǎn)隨機(jī)部署在正方形監(jiān)測(cè)區(qū)域，部署完成后不能移動(dòng)；

(2) 匯聚節(jié)點(diǎn)位于正方形網(wǎng)絡(luò)的中心，能量沒(méi)有限制；

(3) 網(wǎng)絡(luò)通信信道是對(duì)稱(chēng)的雙信道；

(4) 節(jié)點(diǎn)可以根據(jù)RSSI(received signal strength indication)計(jì)算兩節(jié)點(diǎn)間的距離，可以根據(jù)需求調(diào)整發(fā)射功率；

(5) 節(jié)點(diǎn)可以根據(jù)監(jiān)測(cè)區(qū)域的劃分感知自己的位置信息，并獲得唯一的身份標(biāo)識(shí).

1.2 能量模型

能耗模型采用經(jīng)典的自由空間和多路徑衰減模型的無(wú)線電模型[8].將l比特的數(shù)據(jù)傳輸距離d所消耗的能量為

(1)

節(jié)點(diǎn)接收l(shuí)比特的數(shù)據(jù)所消耗的能量[9]為

ERx=lEelec.

(2)

其中：ETx表示節(jié)點(diǎn)發(fā)送數(shù)據(jù)的能耗；ERx表示節(jié)點(diǎn)接收數(shù)據(jù)的能耗；Eelec表示節(jié)點(diǎn)發(fā)送或接收l(shuí)比特?cái)?shù)據(jù)電路消耗的能量；εfs表示節(jié)點(diǎn)在放大自由空間模型中的能耗系數(shù)；εmp表示多路徑衰減模型中的能耗系數(shù).

利用無(wú)線數(shù)據(jù)傳輸?shù)奶攸c(diǎn)，無(wú)線傳感器網(wǎng)絡(luò)路由算法可以讓大規(guī)模數(shù)據(jù)能夠安全有效地進(jìn)行無(wú)線傳輸[10].下面將對(duì)改進(jìn)的路由算法作詳細(xì)介紹.

2 加權(quán)優(yōu)化樹(shù)分簇路由算法

2.1 路由算法思想

為了解決無(wú)線傳感器網(wǎng)絡(luò)中存在的能耗問(wèn)題，增加網(wǎng)絡(luò)的生存時(shí)間，本文提出一種加權(quán)優(yōu)化樹(shù)分簇路由算法——WOTC(weighted optimal tree clustering)，對(duì)樹(shù)型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)[11]進(jìn)行加權(quán)優(yōu)化，形成最小傳輸代價(jià)樹(shù)型結(jié)構(gòu)，并將其應(yīng)用于分簇路由算法[12]中.

WOTC主要思想是：先對(duì)監(jiān)測(cè)區(qū)域進(jìn)行分區(qū)；然后在分區(qū)內(nèi)的各個(gè)節(jié)點(diǎn)根據(jù)自己的通信范圍建立自己的鄰居表，再以數(shù)據(jù)傳輸代價(jià)為依據(jù)，在分區(qū)內(nèi)構(gòu)建加權(quán)優(yōu)化的樹(shù)型結(jié)構(gòu)(樹(shù)形結(jié)構(gòu)分為樹(shù)干、樹(shù)枝、樹(shù)葉節(jié)點(diǎn)三層結(jié)構(gòu))；最終數(shù)據(jù)從各個(gè)節(jié)點(diǎn)傳輸至分區(qū)內(nèi)樹(shù)型結(jié)構(gòu)的根節(jié)點(diǎn)，即此分區(qū)的簇頭節(jié)點(diǎn)，并由簇頭節(jié)點(diǎn)將數(shù)據(jù)傳送至匯聚節(jié)點(diǎn).下文中簇頭節(jié)點(diǎn)即為分區(qū)內(nèi)樹(shù)的根節(jié)點(diǎn).通過(guò)對(duì)監(jiān)測(cè)區(qū)域進(jìn)行分區(qū)并將改進(jìn)的最小傳輸代價(jià)樹(shù)型結(jié)構(gòu)應(yīng)用于分簇路由算法中，解決了普通節(jié)點(diǎn)與簇頭距離過(guò)長(zhǎng)導(dǎo)致的數(shù)據(jù)傳輸能耗問(wèn)題，也有效防止了樹(shù)的深度過(guò)大導(dǎo)致的長(zhǎng)鏈問(wèn)題[13].

2.2 路由算法的計(jì)算方法

2.2.1 最小剩余能量

在無(wú)線傳感器網(wǎng)絡(luò)中，由于節(jié)點(diǎn)分布不均勻，在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中所處的位置不同，所以節(jié)點(diǎn)功能和轉(zhuǎn)發(fā)的數(shù)據(jù)量有所不同.如果在設(shè)置最小能量閾值時(shí)采用同一固定值，則會(huì)出現(xiàn)節(jié)點(diǎn)過(guò)早死亡的情況.于是需分層次設(shè)置最小剩余能量閾值.越靠近匯聚節(jié)點(diǎn)的節(jié)點(diǎn)會(huì)轉(zhuǎn)發(fā)更多的數(shù)據(jù)，其單位工作時(shí)間內(nèi)消耗更多的能量，其最小剩余能量閥值應(yīng)該越大.本文對(duì)文獻(xiàn)[14]的最小剩余能量進(jìn)行改進(jìn)，將節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)目考慮在內(nèi)，則任一節(jié)點(diǎn)最小剩余能量為

(3)

其中：E0為初始能量；di為節(jié)點(diǎn)在樹(shù)形結(jié)構(gòu)中的層次；b為子節(jié)點(diǎn)的數(shù)目；a為調(diào)整取值的系數(shù).用Eres表示節(jié)點(diǎn)剩余能量，當(dāng)Eres

2.2.2 數(shù)據(jù)傳輸代價(jià)

改進(jìn)的WOTC算法拓?fù)浣Y(jié)構(gòu)的建立首先需要計(jì)算節(jié)點(diǎn)之間的數(shù)據(jù)傳輸代價(jià)，即將鏈路上節(jié)點(diǎn)的剩余能量、相鄰節(jié)點(diǎn)的距離、與基站的距離及信道質(zhì)量進(jìn)行綜合考慮，計(jì)算出數(shù)據(jù)傳輸需要消耗的資源數(shù)值.數(shù)據(jù)傳輸代價(jià)越小，說(shuō)明節(jié)點(diǎn)間的路徑越有優(yōu)勢(shì).每個(gè)節(jié)點(diǎn)都會(huì)計(jì)算與相鄰節(jié)點(diǎn)的數(shù)據(jù)傳輸代價(jià).這樣能夠更全面地反映鏈路的狀態(tài)，更好地反映數(shù)據(jù)傳輸?shù)那闆r.數(shù)據(jù)傳輸代價(jià)用W表示.表1為計(jì)算W的參數(shù).

表1 數(shù)據(jù)傳輸代價(jià)參數(shù)

W計(jì)算公式如下：

a3Dis+a4D.

(4)

其中:

(1)a1～a4表示非負(fù)權(quán)重系數(shù)，四者之和為1.權(quán)重系數(shù)的選擇采用層次分析法確定，整合研究人員的主觀判斷，使定性分析與定量分析相結(jié)合，更好地表示出影響因素所占的比重.經(jīng)計(jì)算得出：a1=0.45，a2=0.25，a3=0.25，a4=0.05.

(3)Dis為節(jié)點(diǎn)與基站的距離，與基站距離較近則消耗能量較少.

(4)D表示與相鄰節(jié)點(diǎn)的距離，與相鄰節(jié)點(diǎn)距離越近則傳輸能耗越少.

定義節(jié)點(diǎn)j的鄰居節(jié)點(diǎn)數(shù)N(i)：

(5)

當(dāng)節(jié)點(diǎn)i與節(jié)點(diǎn)j的距離小于節(jié)點(diǎn)的通信范圍并且節(jié)點(diǎn)i的能量大于0，則認(rèn)為節(jié)點(diǎn)i是節(jié)點(diǎn)j的鄰居節(jié)點(diǎn).

隨著網(wǎng)絡(luò)節(jié)點(diǎn)不斷傳輸數(shù)據(jù)，節(jié)點(diǎn)的狀態(tài)會(huì)發(fā)生改變,節(jié)點(diǎn)間的數(shù)據(jù)傳輸代價(jià)也會(huì)變化，當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)發(fā)生變化時(shí)會(huì)重新計(jì)算其傳輸代價(jià).

在理論上，傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳輸代價(jià)表示兩個(gè)節(jié)點(diǎn)之間的歐幾里德距離，但如上面所示，必須考慮到節(jié)點(diǎn)的狀態(tài)，如剩余能量、傳輸過(guò)程中造成的路徑損耗和信號(hào)衰減、與基站及相鄰節(jié)點(diǎn)的距離等，所以對(duì)傳輸代價(jià)的計(jì)算方法進(jìn)行了定義.傳輸代價(jià)越大表示其傳輸成本越大，路徑消耗也就越大，不是最優(yōu)路徑.

2.3 路由算法過(guò)程

2.3.1 區(qū)域的劃分

為了減少樹(shù)型結(jié)構(gòu)的深度，避免長(zhǎng)鏈及壞鏈的形成，WOTC算法首先對(duì)監(jiān)測(cè)區(qū)域進(jìn)行劃分，即對(duì)監(jiān)測(cè)區(qū)域進(jìn)行分簇.

考慮節(jié)點(diǎn)分布的密集程度，依據(jù)區(qū)域中節(jié)點(diǎn)的密集度,動(dòng)態(tài)對(duì)監(jiān)測(cè)區(qū)域進(jìn)行劃分.首先,將監(jiān)測(cè)區(qū)域分為4個(gè)相同的正方形區(qū)域，用分區(qū)號(hào)1～4來(lái)表示，并將分區(qū)號(hào)存入節(jié)點(diǎn)的區(qū)域標(biāo)記中.其次，匯聚節(jié)點(diǎn)在監(jiān)測(cè)區(qū)域的中心位置.最后，計(jì)算各區(qū)域節(jié)點(diǎn)的密集度，用單位面積的節(jié)點(diǎn)數(shù)來(lái)表示.

其中子分區(qū)數(shù)即為簇的數(shù)目，節(jié)點(diǎn)在各分區(qū)內(nèi)自組織形成簇.在網(wǎng)絡(luò)初始化時(shí)，規(guī)定以匯聚節(jié)點(diǎn)為原點(diǎn)，建立橫縱坐標(biāo)軸來(lái)確定各節(jié)點(diǎn)的相對(duì)物理位置，并獲得各自的物理地址，即節(jié)點(diǎn)唯一的ID.節(jié)點(diǎn)形成樹(shù)型網(wǎng)絡(luò)拓?fù)鋾r(shí)分配樹(shù)型結(jié)構(gòu)的地址，用于區(qū)分節(jié)點(diǎn)的層次及類(lèi)型.各個(gè)節(jié)點(diǎn)將自身感知的位置信息發(fā)送給匯聚節(jié)點(diǎn)，來(lái)獲得自身所處的分區(qū)信息，以便匯聚節(jié)點(diǎn)更好地掌握網(wǎng)絡(luò)中節(jié)點(diǎn)的分布情況，為之后網(wǎng)絡(luò)結(jié)構(gòu)的形成提供條件.

分區(qū)的結(jié)構(gòu)如圖1所示.監(jiān)測(cè)區(qū)域被劃分為1～4區(qū)域，每個(gè)區(qū)域?yàn)橐粋€(gè)簇，簇內(nèi)節(jié)點(diǎn)自組織形成網(wǎng)絡(luò).如果某一區(qū)域的節(jié)點(diǎn)過(guò)于密集，即節(jié)點(diǎn)密度大于額定值(額定值由監(jiān)測(cè)區(qū)域的總面積和總節(jié)點(diǎn)數(shù)來(lái)確定)的1.5倍時(shí)，則對(duì)該區(qū)域進(jìn)行再次分區(qū)，將此區(qū)域分為2個(gè)大小相等的三角形區(qū)域.按照這種動(dòng)態(tài)劃分規(guī)則將整個(gè)監(jiān)測(cè)區(qū)域分為較小且能覆蓋全部監(jiān)測(cè)區(qū)域的子區(qū)域.圖2為對(duì)節(jié)點(diǎn)密度過(guò)大的區(qū)域1進(jìn)行重新分區(qū)的示例.

圖1 區(qū)域劃分

圖2 區(qū)域二次劃分

此時(shí)區(qū)域1由于節(jié)點(diǎn)密度過(guò)大被重新劃分為2個(gè)子區(qū)域，區(qū)域內(nèi)的節(jié)點(diǎn)根據(jù)所處的位置重新進(jìn)行區(qū)域的標(biāo)記，并且子區(qū)域內(nèi)節(jié)點(diǎn)自組織形成網(wǎng)絡(luò)結(jié)構(gòu).

2.3.2 鄰居表建立

首先，位于監(jiān)測(cè)區(qū)域中心的匯聚節(jié)點(diǎn)以可以覆蓋整個(gè)監(jiān)測(cè)區(qū)域的功率向網(wǎng)絡(luò)中的節(jié)點(diǎn)發(fā)送測(cè)試報(bào)文；然后，區(qū)域中的各個(gè)節(jié)點(diǎn)根據(jù)接收到的報(bào)文功率的大小及方向確定自己距離基站的距離及自身所處的區(qū)域.

當(dāng)區(qū)域劃分完畢后，節(jié)點(diǎn)首先向周?chē)?jié)點(diǎn)廣播自身信息，其廣播報(bào)文格式如下：

TypeS_IDEnergyDis

其字段信息如下：

Type：表示報(bào)文的格式；

S_ID：本節(jié)點(diǎn)的ID；

Energy：本節(jié)點(diǎn)的剩余能量；

Dis：與基站的距離.

所有節(jié)點(diǎn)都向周?chē)従庸?jié)點(diǎn)發(fā)送此廣播信息.當(dāng)鄰居節(jié)點(diǎn)收到此信息后，首先在鄰居表中搜索是否存在此節(jié)點(diǎn)，如果節(jié)點(diǎn)在鄰居表中不存在，則節(jié)點(diǎn)根據(jù)接收到報(bào)文信息的功率計(jì)算距離本節(jié)點(diǎn)的距離，把此節(jié)點(diǎn)信息加入到鄰居表中，并且把鄰居數(shù)加1.然后發(fā)送反饋信息給源節(jié)點(diǎn)，源節(jié)點(diǎn)同樣根據(jù)信息的功率計(jì)算與鄰居節(jié)點(diǎn)的距離，存入自己的鄰居表中，并且鄰居數(shù)同樣加1.節(jié)點(diǎn)的鄰居表中字段結(jié)構(gòu)如下：

NeighborIDLevelEnergyDisDType

鄰居表中各字段信息段如下：

NeighborID：鄰居節(jié)點(diǎn)的ID；

Level：節(jié)點(diǎn)在網(wǎng)絡(luò)結(jié)構(gòu)所處的深度，即節(jié)點(diǎn)在樹(shù)型結(jié)構(gòu)中所使用的地址；

Energy：節(jié)點(diǎn)的剩余能量；

Dis：節(jié)點(diǎn)距離基站的距離；

D：與鄰居節(jié)點(diǎn)的距離；

Type：節(jié)點(diǎn)之間的關(guān)系，如父節(jié)點(diǎn)、子節(jié)點(diǎn)、其余節(jié)點(diǎn).

此時(shí)Level值為空，因?yàn)榇藭r(shí)還沒(méi)有形成樹(shù)型結(jié)構(gòu)，所以該信息字段為空.當(dāng)形成樹(shù)型結(jié)構(gòu)時(shí)，根據(jù)節(jié)點(diǎn)在樹(shù)型結(jié)構(gòu)中的深度和加入樹(shù)型結(jié)構(gòu)的先后順序，計(jì)算其虛擬的網(wǎng)絡(luò)結(jié)構(gòu)地址，存入此字段；Type字段為空，當(dāng)形成樹(shù)型結(jié)構(gòu)時(shí)，節(jié)點(diǎn)根據(jù)是父節(jié)點(diǎn)、子節(jié)點(diǎn)或是其他節(jié)點(diǎn)將此信息存入此字段.

當(dāng)節(jié)點(diǎn)范圍內(nèi)的其他節(jié)點(diǎn)都加入各自的鄰居表后，鄰居搜索過(guò)程完成，進(jìn)入生成樹(shù)的構(gòu)建階段.

2.3.3 簇內(nèi)生成樹(shù)結(jié)構(gòu)的建立

在節(jié)點(diǎn)鄰居表完成后，便開(kāi)始生成樹(shù)的建立.此時(shí)各區(qū)域中的節(jié)點(diǎn)首先選取簇頭，然后計(jì)算節(jié)點(diǎn)間的數(shù)據(jù)傳輸代價(jià)，并建立加權(quán)優(yōu)化的樹(shù)型拓?fù)浣Y(jié)構(gòu).具體過(guò)程如下：

(1) 簇頭的選取

在改進(jìn)的WOTC算法中，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)規(guī)定簇頭直接與匯聚節(jié)點(diǎn)進(jìn)行通信，將本簇中收集的數(shù)據(jù)發(fā)送出去，這種通信方式?jīng)Q定了簇頭節(jié)點(diǎn)本身的能量消耗高于普通的節(jié)點(diǎn).如果簇頭距離匯聚節(jié)點(diǎn)太遠(yuǎn)，則導(dǎo)致能量快速消耗，造成簇頭節(jié)點(diǎn)的過(guò)早死亡.這樣網(wǎng)絡(luò)就會(huì)頻繁進(jìn)行網(wǎng)絡(luò)的重構(gòu)，降低網(wǎng)絡(luò)的可用性.所以簇頭作為生成樹(shù)結(jié)構(gòu)的根節(jié)點(diǎn)，其選取的機(jī)制是將靠近匯聚節(jié)點(diǎn)且能量高的節(jié)點(diǎn)作為樹(shù)的根節(jié)點(diǎn).

簇頭節(jié)點(diǎn)選取如圖3所示.

圖3 簇頭的選取

簇頭節(jié)點(diǎn)為距離匯聚節(jié)點(diǎn)較近且能量較高的節(jié)點(diǎn)，在與匯聚節(jié)點(diǎn)進(jìn)行數(shù)據(jù)傳輸?shù)臅r(shí)候能夠減少數(shù)據(jù)傳輸過(guò)程中消耗的能量，增加網(wǎng)絡(luò)的生存時(shí)間.

(2) 生成樹(shù)的建立

當(dāng)節(jié)點(diǎn)鄰居搜索過(guò)程完成后，節(jié)點(diǎn)根據(jù)上節(jié)所定義的計(jì)算方法計(jì)算節(jié)點(diǎn)間的數(shù)據(jù)傳輸代價(jià)，然后據(jù)此構(gòu)建生成樹(shù)結(jié)構(gòu)，此樹(shù)結(jié)構(gòu)分為樹(shù)干節(jié)點(diǎn)、樹(shù)枝節(jié)點(diǎn)、樹(shù)葉節(jié)點(diǎn).先生成樹(shù)干，然后再生成樹(shù)枝和樹(shù)葉節(jié)點(diǎn).

(a)樹(shù)干節(jié)點(diǎn)建立

按照上節(jié)定義的簇頭選取方法選取各區(qū)域的簇頭，然后從簇頭開(kāi)始，根據(jù)計(jì)算的數(shù)據(jù)傳輸代價(jià)，選擇向最小數(shù)據(jù)傳輸代價(jià)的節(jié)點(diǎn)發(fā)送請(qǐng)求消息，請(qǐng)求加入樹(shù)干，并把自己的Level值設(shè)為1.當(dāng)節(jié)點(diǎn)滿(mǎn)足最小剩余能量的要求時(shí)，則加入樹(shù)干，將本節(jié)點(diǎn)的Level值加1，并且在之后用點(diǎn)分隔再加一位表示加入的順序.例如，除了簇頭之外第一個(gè)加入樹(shù)干的節(jié)點(diǎn)其Level值為2.0，表示是樹(shù)型結(jié)構(gòu)的第2層，并且是第一個(gè)加入第二層的節(jié)點(diǎn)，為樹(shù)干節(jié)點(diǎn)，分隔符點(diǎn)之后為0的都表示樹(shù)干節(jié)點(diǎn).然后節(jié)點(diǎn)將上一跳節(jié)點(diǎn)即簇頭節(jié)點(diǎn)的Level值存入鄰居表，把Type字段也存入自己鄰居表，簇頭節(jié)點(diǎn)為此節(jié)點(diǎn)的父節(jié)點(diǎn)，所以在鄰居表中存為isfather.至此，節(jié)點(diǎn)鄰居表中的數(shù)據(jù)字段全部填寫(xiě)完成.

此節(jié)點(diǎn)再向自己鄰居表中的數(shù)據(jù)傳輸代價(jià)最小的節(jié)點(diǎn)發(fā)送請(qǐng)求加入消息，滿(mǎn)足要求后加入樹(shù)干，并且將自己Level值更新為3.0，將上一跳節(jié)點(diǎn)的Level值存入鄰居表，上一跳節(jié)點(diǎn)也同時(shí)將此節(jié)點(diǎn)Level值存入鄰居表；然后在鄰居表中將上一跳節(jié)點(diǎn)的Type字段更新為isfather，同時(shí)上一跳節(jié)點(diǎn)在鄰居表中把本節(jié)點(diǎn)的Type值更新為isson.按照此方法進(jìn)行樹(shù)型結(jié)構(gòu)中樹(shù)干的構(gòu)建，直至最后一個(gè)樹(shù)干節(jié)點(diǎn)加入.在此以一個(gè)區(qū)域?yàn)槔?，其?shù)干節(jié)點(diǎn)結(jié)構(gòu)如圖4所示.

圖4 樹(shù)干節(jié)點(diǎn)

圖4節(jié)點(diǎn)中標(biāo)記的值為節(jié)點(diǎn)的Level值，即在樹(shù)型結(jié)構(gòu)中所處的深度.其中1為此區(qū)域的簇頭節(jié)點(diǎn)，2.0表示深度為2，且第二個(gè)加入樹(shù)型結(jié)構(gòu)的樹(shù)干節(jié)點(diǎn)，依次類(lèi)推，8.0為深度為8，且最后一個(gè)加入樹(shù)型結(jié)構(gòu)的樹(shù)干節(jié)點(diǎn).至此，樹(shù)干結(jié)構(gòu)構(gòu)建完成.

(b)樹(shù)枝節(jié)點(diǎn)的建立

當(dāng)樹(shù)干節(jié)點(diǎn)構(gòu)建完成后，節(jié)點(diǎn)向周?chē)?jié)點(diǎn)廣播自己當(dāng)選樹(shù)干節(jié)點(diǎn)的消息.周?chē)?jié)點(diǎn)接收到此信息后，在自己鄰居表進(jìn)行搜索，當(dāng)樹(shù)干節(jié)點(diǎn)是鄰居表中數(shù)據(jù)傳輸代價(jià)最小的節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)向樹(shù)干節(jié)點(diǎn)發(fā)出請(qǐng)求加入的消息，當(dāng)滿(mǎn)足剩余能量最小的要求時(shí)，成功加入樹(shù)型結(jié)構(gòu)，并且其Level值為其連接的樹(shù)干節(jié)點(diǎn)即其父節(jié)點(diǎn)的Level值加1，分隔符后根據(jù)其加入樹(shù)型結(jié)構(gòu)的順序進(jìn)行編號(hào)1、2、3等.比如與Level值為2.0的樹(shù)干節(jié)點(diǎn)相連接的第一個(gè)樹(shù)枝節(jié)點(diǎn)，其Level值為3.1，表示其樹(shù)型深度為3，是第一個(gè)加入此樹(shù)干的樹(shù)枝節(jié)點(diǎn)，直至所有樹(shù)枝節(jié)點(diǎn)加入樹(shù)干.其結(jié)構(gòu)如圖5所示.

圖5 樹(shù)枝節(jié)點(diǎn)

圖5中所有分隔符后為0的為樹(shù)干節(jié)點(diǎn)，為1的為樹(shù)枝節(jié)點(diǎn)，空白的為未加入樹(shù)型結(jié)構(gòu)的節(jié)點(diǎn).

(c)樹(shù)葉節(jié)點(diǎn)的建立

當(dāng)樹(shù)枝節(jié)點(diǎn)建立完成后，節(jié)點(diǎn)同樣向鄰居表中的節(jié)點(diǎn)發(fā)送廣播消息告知自己當(dāng)選為樹(shù)枝節(jié)點(diǎn).鄰居表中未加入樹(shù)型結(jié)構(gòu)的節(jié)點(diǎn)對(duì)鄰居表進(jìn)行搜索，當(dāng)數(shù)據(jù)傳輸代價(jià)最小的節(jié)點(diǎn)為樹(shù)枝節(jié)點(diǎn)時(shí)，未加入樹(shù)型結(jié)構(gòu)的節(jié)點(diǎn)向此樹(shù)枝節(jié)點(diǎn)發(fā)送請(qǐng)求加入的消息，當(dāng)節(jié)點(diǎn)滿(mǎn)足最小剩余能量的要求時(shí)，加入樹(shù)型結(jié)構(gòu)，成為樹(shù)葉節(jié)點(diǎn)，其地址為上一跳樹(shù)枝節(jié)點(diǎn)即父節(jié)點(diǎn)的深度加1，并且再增加一位標(biāo)志位，并根據(jù)加入的順序進(jìn)行編號(hào)，以區(qū)分不同樹(shù)葉節(jié)點(diǎn).如4.1節(jié)點(diǎn)第一個(gè)樹(shù)葉節(jié)點(diǎn)地址為5.1.1，表示其樹(shù)型結(jié)構(gòu)的深度為5，為此樹(shù)枝節(jié)點(diǎn)的第一個(gè)樹(shù)葉節(jié)點(diǎn).按照此方法直至所有節(jié)點(diǎn)都已加入樹(shù)結(jié)構(gòu).當(dāng)根據(jù)樹(shù)葉節(jié)點(diǎn)地址推算其樹(shù)枝節(jié)點(diǎn)地址時(shí)，把深度減1，然后去掉最后一位即是樹(shù)枝節(jié)點(diǎn)地址.其樹(shù)型結(jié)構(gòu)如圖6所示.

圖6 樹(shù)葉節(jié)點(diǎn)

如圖6所示：所有節(jié)點(diǎn)均已加入樹(shù)型結(jié)構(gòu)，樹(shù)干節(jié)點(diǎn)地址為兩位并且最后一位為0；樹(shù)枝節(jié)點(diǎn)同樣為兩位，最后一位按加入樹(shù)干的順序排列，圖中僅標(biāo)示出第一個(gè)加入樹(shù)型結(jié)構(gòu)的樹(shù)干節(jié)點(diǎn)，故最后一位均為1；樹(shù)葉節(jié)點(diǎn)地址為三位或三位以上，最后一位為加入樹(shù)枝節(jié)點(diǎn)的順序，圖中僅標(biāo)示出第一個(gè)加入樹(shù)型結(jié)構(gòu)的樹(shù)葉節(jié)點(diǎn)，故最后一位均為1.至此，分區(qū)內(nèi)的樹(shù)型結(jié)構(gòu)構(gòu)建完成.

2.3.4 路由算法的描述

V代表傳感器節(jié)點(diǎn)，W代表兩節(jié)點(diǎn)間的數(shù)據(jù)傳輸代價(jià)，則數(shù)據(jù)傳輸?shù)闹饕襟E如下:

(1) 根據(jù)上述最小傳輸代價(jià)樹(shù)型結(jié)構(gòu)，在數(shù)據(jù)包中增加節(jié)點(diǎn)最小剩余能量Emin、節(jié)點(diǎn)間的數(shù)據(jù)傳輸代價(jià)值W；

(2) 節(jié)點(diǎn)開(kāi)啟一個(gè)定時(shí)器，接收此時(shí)間內(nèi)收到的Request消息，形成鄰居表；

(3) 節(jié)點(diǎn)根據(jù)鄰居表中信息計(jì)算節(jié)點(diǎn)間的數(shù)據(jù)傳輸代價(jià)，并根據(jù)上節(jié)所述規(guī)則進(jìn)行處理；

(4) 根據(jù)定義好的規(guī)則建立生成樹(shù)結(jié)構(gòu)、建立傳輸路徑，進(jìn)行數(shù)據(jù)傳輸.

節(jié)點(diǎn)數(shù)據(jù)傳輸代價(jià)將節(jié)點(diǎn)之間距離、距離基站距離、鏈路質(zhì)量、剩余能量等參數(shù)進(jìn)行綜合考慮.下面為路由算法描述的偽代碼：

輸入：節(jié)點(diǎn)的集合

輸出：生成的邏輯樹(shù)

ForVfrom 1 toNdo

T=0

Subregion of nodes

Continue；

For each vertexV

Send Broadcast message to Adjacent node

Form a neighbor table based on node information

For each vertexV

Calculating the cost of data trans-

missionWbetween nodes

Sort theWof Nodesorder byWin

the Neighbor table

For(i=1,i<=N,i++)

select the next smallestWNode betweenVif(No cycle is creat)T

returnT

returnT

end for

通過(guò)這種改進(jìn)，綜合考慮節(jié)點(diǎn)剩余能量和節(jié)點(diǎn)間距離，確定使用數(shù)據(jù)傳輸代價(jià)最小的節(jié)點(diǎn)來(lái)轉(zhuǎn)發(fā)數(shù)據(jù)，均衡了網(wǎng)絡(luò)整體能耗，提高了數(shù)據(jù)傳輸效率.

2.4 拓?fù)浣Y(jié)構(gòu)聲明周期的控制

設(shè)定網(wǎng)絡(luò)中只有一個(gè)匯聚節(jié)點(diǎn)，與傳統(tǒng)的簇樹(shù)結(jié)構(gòu)不同，先設(shè)定兩個(gè)時(shí)間t1、t2,在t1時(shí)間范圍內(nèi)時(shí)，當(dāng)一個(gè)節(jié)點(diǎn)請(qǐng)求加入網(wǎng)絡(luò)，先分配給節(jié)點(diǎn)一個(gè)id，然后加入節(jié)點(diǎn)的鄰居表.過(guò)了時(shí)間t1，在時(shí)間t2范圍內(nèi)時(shí)，按上述算法形成拓?fù)浣Y(jié)構(gòu)，但不再接收加入鄰居表的請(qǐng)求，把這些請(qǐng)求消息儲(chǔ)存在臨時(shí)表里.這樣會(huì)減少能量的消耗，增加傳輸效率[16].因?yàn)槿绻姓?qǐng)求就重新進(jìn)行拓?fù)浣Y(jié)構(gòu)的構(gòu)建，中間會(huì)不斷進(jìn)行重構(gòu)，會(huì)帶來(lái)地址重新分配等的若干計(jì)算，浪費(fèi)能量，降低效率.拓?fù)渲芷诹鞒倘鐖D7所示.其中節(jié)點(diǎn)接收數(shù)據(jù)和接收請(qǐng)求，再根據(jù)數(shù)據(jù)包的內(nèi)容區(qū)分為數(shù)據(jù)還是請(qǐng)求.

圖7 拓?fù)渲芷?/p>

當(dāng)傳感器網(wǎng)絡(luò)中所有節(jié)點(diǎn)狀態(tài)都正常時(shí)，會(huì)按照流程運(yùn)行.如果一個(gè)節(jié)點(diǎn)在一段時(shí)間內(nèi)由于任何原因與匯聚節(jié)點(diǎn)失去聯(lián)系，將認(rèn)為該節(jié)點(diǎn)已經(jīng)死亡.當(dāng)死亡節(jié)點(diǎn)是樹(shù)葉節(jié)點(diǎn)，網(wǎng)絡(luò)繼續(xù)工作；當(dāng)死亡節(jié)點(diǎn)是樹(shù)枝節(jié)點(diǎn)，則重新選擇合適的樹(shù)枝節(jié)點(diǎn)加入樹(shù)干，在小范圍內(nèi)進(jìn)行調(diào)整；當(dāng)死亡節(jié)點(diǎn)為樹(shù)干節(jié)點(diǎn)，則重新選取樹(shù)干節(jié)點(diǎn)進(jìn)行代替，并且此樹(shù)干節(jié)點(diǎn)之后的樹(shù)干節(jié)點(diǎn)都要重新進(jìn)行選取，更新樹(shù)型結(jié)構(gòu)的地址，在較大范圍內(nèi)進(jìn)行網(wǎng)絡(luò)的重構(gòu).通過(guò)這種方式建立了一個(gè)分布式獨(dú)立的能源高效網(wǎng)絡(luò)，而且節(jié)點(diǎn)間的數(shù)據(jù)傳輸代價(jià)小.

3 仿真分析

為了評(píng)估改進(jìn)后算法的性能，應(yīng)用NS2對(duì)經(jīng)典LEACH算法、EEUC算法及改進(jìn)算法進(jìn)行網(wǎng)絡(luò)仿真分析.其網(wǎng)絡(luò)環(huán)境設(shè)置如下：設(shè)定仿真環(huán)境區(qū)域?yàn)?00 m×200 m，網(wǎng)絡(luò)中隨機(jī)分布的WSN傳感器節(jié)點(diǎn)個(gè)數(shù)為100個(gè)，將節(jié)點(diǎn)初始能量設(shè)置為2 J，節(jié)點(diǎn)發(fā)射功率為0.6 W，接收功率為0.3 W，發(fā)送數(shù)據(jù)包大小為512 bit，網(wǎng)絡(luò)中的基站處于區(qū)域的中心位置.

圖8中表示了網(wǎng)絡(luò)中存活節(jié)點(diǎn)數(shù)量隨網(wǎng)絡(luò)仿真時(shí)間的變化情況.由圖8可以看出：傳統(tǒng)的LEACH算法中出現(xiàn)死亡節(jié)點(diǎn)的時(shí)間較早，在200輪之后節(jié)點(diǎn)開(kāi)始死亡；EEUC算法在節(jié)點(diǎn)能耗方面得到改進(jìn)，在600輪左右開(kāi)始出現(xiàn)死亡節(jié)點(diǎn)；改進(jìn)的WOTC網(wǎng)絡(luò)結(jié)構(gòu)中節(jié)點(diǎn)死亡時(shí)間較晚，在節(jié)點(diǎn)能耗方面有了明顯的改進(jìn).網(wǎng)絡(luò)中一半節(jié)點(diǎn)的死亡時(shí)間LEACH算法最早，EEUC算法次之，WOTC算法最晚.可以看出改進(jìn)的WOTC結(jié)構(gòu)使網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗更加均衡，避免了節(jié)點(diǎn)的過(guò)早死亡，增加了傳感器網(wǎng)絡(luò)的有效存活時(shí)間，很大程度上提高了網(wǎng)絡(luò)的穩(wěn)定性.

圖8 網(wǎng)絡(luò)中節(jié)點(diǎn)存活數(shù)量對(duì)比

圖9表示了網(wǎng)絡(luò)能量消耗隨網(wǎng)絡(luò)仿真時(shí)間的變化情況.

圖9 網(wǎng)絡(luò)能量消耗隨仿真時(shí)間的變化

由圖9可以看出：隨著運(yùn)行時(shí)間的增加，LEACH算法能量消耗最多，EEUC次之，改進(jìn)的WOTC算法整體的網(wǎng)絡(luò)能耗最小.WOTC通過(guò)對(duì)監(jiān)測(cè)區(qū)域進(jìn)行分區(qū)、對(duì)分區(qū)內(nèi)傳輸路徑的通信代價(jià)進(jìn)行優(yōu)化并采用加權(quán)優(yōu)化的樹(shù)形結(jié)構(gòu)，使得網(wǎng)絡(luò)中能耗趨于平緩狀態(tài)，平衡了網(wǎng)絡(luò)整體的能量消耗，提高了網(wǎng)絡(luò)的性能.

4 結(jié)束語(yǔ)

目前無(wú)線傳感器網(wǎng)絡(luò)技術(shù)已經(jīng)得到了廣泛的應(yīng)用.本文在經(jīng)典的WSN路由算法以及改進(jìn)的研究成果的基礎(chǔ)上，提出了一種改進(jìn)的加權(quán)優(yōu)化樹(shù)型結(jié)構(gòu)的WSN分簇路由算法.通過(guò)計(jì)算數(shù)據(jù)傳輸代價(jià)，對(duì)樹(shù)型拓?fù)浣Y(jié)構(gòu)進(jìn)行加權(quán)優(yōu)化，形成最小傳輸代價(jià)樹(shù)的結(jié)構(gòu)，并應(yīng)用于分簇路由算法中，平衡了網(wǎng)絡(luò)的能量消耗，增加了網(wǎng)絡(luò)的生存時(shí)間.由于對(duì)數(shù)據(jù)傳輸路徑進(jìn)行優(yōu)化，額外增加了控制和計(jì)算的開(kāi)銷(xiāo)，但整體上提升了網(wǎng)絡(luò)的性能.下一步的研究工作將會(huì)在本文研究的基礎(chǔ)上，對(duì)算法的時(shí)延進(jìn)行優(yōu)化，增加網(wǎng)絡(luò)的吞吐量，并進(jìn)行驗(yàn)證.