無(wú)線傳感器網(wǎng)絡(luò)中分布式多跳路由算法研究*

尚鳳軍，任東海

(重慶郵電大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，重慶 400065)

在當(dāng)今信息技術(shù)飛速發(fā)展的時(shí)代，互聯(lián)網(wǎng)為人們提供了快捷的通信平臺(tái)，極大地方便了人們的信息交流，無(wú)線傳感器網(wǎng)絡(luò)技術(shù)的產(chǎn)生將徹底改變?nèi)祟愖怨乓詠?lái)僅僅靠自身的觸覺(jué)、視覺(jué)、嗅覺(jué)來(lái)感知信息的現(xiàn)狀，極大的提高人類獲取信息的準(zhǔn)確性和靈敏度［1］。作為信息時(shí)代的一項(xiàng)變革性的技術(shù)，無(wú)線傳感器網(wǎng)絡(luò)可以使人們?cè)谌魏螘r(shí)間、任何地點(diǎn)和任何環(huán)境條件下獲取大量詳實(shí)、可靠的信息，真正實(shí)現(xiàn)“無(wú)處不在的計(jì)算”理念。無(wú)線傳感器網(wǎng)絡(luò)是計(jì)算機(jī)科學(xué)技術(shù)的一個(gè)新的研究領(lǐng)域，具有十分廣闊的應(yīng)用前景，它的出現(xiàn)引起了全世界范圍的廣泛關(guān)注［2］。美國(guó)《商業(yè)周刊》將無(wú)線傳感器網(wǎng)絡(luò)列為21世紀(jì)高技術(shù)領(lǐng)域中的四大支柱型產(chǎn)業(yè)之一；《技術(shù)評(píng)論》雜志也將其列為未來(lái)改變世界的10大新興技術(shù)之首。可以預(yù)言，無(wú)線傳感器網(wǎng)絡(luò)的發(fā)展和廣泛應(yīng)用，將對(duì)人們的社會(huì)生活和產(chǎn)業(yè)變革帶來(lái)極大的影響和產(chǎn)生巨大的推動(dòng)力。

1 基于退避機(jī)制的成簇算法(CHTD)

目前，已經(jīng)存在多種關(guān)于無(wú)線傳感器網(wǎng)絡(luò)分簇算法的研究。在文獻(xiàn)［3－4］都提到使用時(shí)間延遲機(jī)制來(lái)選擇簇頭，通過(guò)給能量較大的節(jié)點(diǎn)設(shè)置較小的等待時(shí)間，從而使剩余能量較多的節(jié)點(diǎn)有較大的概率成為簇頭。然而，文獻(xiàn)［3］并未對(duì)每輪產(chǎn)生的簇頭數(shù)目進(jìn)行研究，若產(chǎn)生簇頭數(shù)目不穩(wěn)定，簇頭能量消耗過(guò)大，進(jìn)而影響網(wǎng)絡(luò)整體的性能。文獻(xiàn)［4］提出的TB-LEACH雖然產(chǎn)生了固定的簇頭數(shù)目，但簇頭的位置分布并不均勻，這樣每個(gè)簇頭管理的成員節(jié)點(diǎn)個(gè)數(shù)不均勻，導(dǎo)致簇與簇之間能量消耗不均勻，網(wǎng)絡(luò)生存時(shí)間就得不到有效延長(zhǎng)，而且沒(méi)有考慮當(dāng)網(wǎng)絡(luò)運(yùn)行初期節(jié)點(diǎn)能量相同的情況下競(jìng)選簇頭發(fā)生的沖突問(wèn)題。在文獻(xiàn)［5］中，作者研究了單跳和多跳成簇模型的花費(fèi)以及分組的聚合問(wèn)題。文獻(xiàn)［6］對(duì)LEACH的簇頭選擇方法進(jìn)行了改進(jìn)，數(shù)據(jù)傳輸采用了單跳和多跳相結(jié)合的方法，提高了系統(tǒng)的能量效率。文獻(xiàn)［7］引入了定時(shí)器方法確定簇頭，保證了能量高的節(jié)點(diǎn)優(yōu)先成為簇頭，提高了網(wǎng)絡(luò)的能量效率。文獻(xiàn)［8］提出了一個(gè)基于能量和到基站距離的分簇算法，并在簇首的數(shù)據(jù)發(fā)送中引入了改進(jìn)的多跳路由算法，提高了基站接收到的數(shù)據(jù)量，延長(zhǎng)了整個(gè)網(wǎng)絡(luò)的壽命。文獻(xiàn)［9］提出了一種非均勻成簇方法，但數(shù)據(jù)傳輸主要考慮單跳方式。文獻(xiàn)［10］提出了一種分環(huán)多跳分簇路由算法，該算法采用分環(huán)的方式實(shí)現(xiàn)簇頭間的多跳通信，通過(guò)在不同環(huán)內(nèi)構(gòu)建大小不同的簇解決傳感器網(wǎng)絡(luò)中存在的“熱點(diǎn)”問(wèn)題，延長(zhǎng)網(wǎng)絡(luò)的生命周期。文獻(xiàn)［11］中綜合考慮網(wǎng)絡(luò)中節(jié)點(diǎn)的剩余能量和節(jié)點(diǎn)問(wèn)傳輸數(shù)據(jù)的能耗，基于最短路徑樹(shù)算法，通過(guò)構(gòu)造兩種不同的權(quán)值函數(shù)，提出了“比例權(quán)值路由算法”，延長(zhǎng)了網(wǎng)絡(luò)生存時(shí)間。但當(dāng)轉(zhuǎn)發(fā)距離較近時(shí)，中間節(jié)點(diǎn)的電路消耗造成的總體能量消耗變大和簇頭節(jié)點(diǎn)在選擇下一跳路由時(shí)，簇頭之間交換信息的開(kāi)銷問(wèn)題，同時(shí)，基于簇的多跳路由算法中簇頭之間和簇與簇之間的能量平衡問(wèn)題也需要進(jìn)一步的改進(jìn)。另外隨著傳感器網(wǎng)絡(luò)應(yīng)用的拓展，QoS路由算法也成為當(dāng)前研究的熱點(diǎn)之一［12］。

為了解決以上問(wèn)題，本文改進(jìn)了節(jié)點(diǎn)的時(shí)間延遲機(jī)制模型并由此得到延遲時(shí)間，使得剩余能量較多的節(jié)點(diǎn)有較小的延遲時(shí)間，考慮到網(wǎng)絡(luò)內(nèi)節(jié)點(diǎn)的能量消耗和負(fù)載均衡，引入了最優(yōu)簇半徑和最佳簇頭數(shù)目作用于簇頭的選擇過(guò)程當(dāng)中，在簇?cái)?shù)據(jù)傳輸過(guò)程中引入多跳機(jī)制，并著重考慮了中間轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇。實(shí)驗(yàn)證明，本算法使得選出的簇頭更適合擔(dān)當(dāng)數(shù)據(jù)轉(zhuǎn)發(fā)任務(wù)，網(wǎng)絡(luò)能量消耗更小，網(wǎng)絡(luò)生命周期進(jìn)一步延長(zhǎng)。

1.1 無(wú)線傳輸能量模型

由于網(wǎng)絡(luò)中路由算法設(shè)計(jì)首要考慮的因素是能量問(wèn)題，所以在無(wú)線傳感器網(wǎng)絡(luò)中，路由算法的設(shè)計(jì)與信道能量損耗模型息息相關(guān)。我們采用與文獻(xiàn)［13］相同的無(wú)線通信能量消耗模型。節(jié)點(diǎn)發(fā)射L比特的數(shù)據(jù)到距離為d的位置，消耗的能量由發(fā)射電路損耗和功率放大損耗兩部分組成，即

其中Eelec表示發(fā)射電路損耗的能量。ξfs、ξmp分別為兩種模型中功率放大所需的能量。d0為一個(gè)距離常數(shù):

距離大于d0時(shí)路徑消耗會(huì)相當(dāng)大，因此一般要求傳輸距離不大于d0，接收k比特的消息，接收機(jī)消耗的能量為:

簇頭節(jié)點(diǎn)進(jìn)行本地處理和數(shù)據(jù)融合的時(shí)候，每處理1比特的數(shù)據(jù)需要的能量損耗EDA。

1.2 CHTD簇頭產(chǎn)生

CHTD算法的執(zhí)行過(guò)程也劃分為“輪”，每一輪分為設(shè)置階段和穩(wěn)定工作階段，在設(shè)置階段所有節(jié)點(diǎn)組織成簇，穩(wěn)定工作階段簇頭把監(jiān)測(cè)的數(shù)據(jù)融合后傳遞到基站。

CHTD算法在每一輪的開(kāi)始，所有節(jié)點(diǎn)并不是立刻就生成隨機(jī)數(shù)，并根據(jù)閥值來(lái)申請(qǐng)簇頭，而是要先根據(jù)式(4)生成一個(gè)定時(shí)器，節(jié)點(diǎn)i在Ttimer(i)秒后超時(shí)。

當(dāng)某一個(gè)節(jié)點(diǎn)延遲時(shí)間到達(dá)時(shí)，它將贏得競(jìng)爭(zhēng)簇頭的權(quán)利，擁有競(jìng)爭(zhēng)權(quán)的節(jié)點(diǎn)通過(guò)自身的簇頭信息集合查看網(wǎng)絡(luò)內(nèi)當(dāng)前簇頭個(gè)數(shù)，若已經(jīng)達(dá)到最佳值，節(jié)點(diǎn)將不再參與簇頭競(jìng)爭(zhēng)，并且通過(guò)信號(hào)接收強(qiáng)度判斷節(jié)點(diǎn)和集合中每個(gè)簇頭節(jié)點(diǎn)之間的距離不小于最優(yōu)簇半徑，保證每輪的簇頭個(gè)數(shù)都是最佳值并且均勻分布在監(jiān)測(cè)的區(qū)域中。

1.3 CHTD簇頭數(shù)量

假設(shè)傳感器節(jié)點(diǎn)隨機(jī)分布在一個(gè)區(qū)域內(nèi)，位于r1區(qū)域的簇頭的個(gè)數(shù)為h1，傳感器節(jié)點(diǎn)的數(shù)量為N1，則每個(gè)簇首的能量消耗由接收所有簇成員的信息、融合這些數(shù)據(jù)、并把融合后的信息傳送給Sink節(jié)點(diǎn)3個(gè)方面組成［13］。我們假設(shè)基站離第1區(qū)域比較近，同樣采用自由空間模型進(jìn)行傳輸，這樣，在一幀中簇首節(jié)點(diǎn)消耗的能量為:

l為每個(gè)數(shù)據(jù)的信息位數(shù)，EDA為數(shù)據(jù)融合的消耗。假設(shè)網(wǎng)絡(luò)中的簇頭節(jié)點(diǎn)都按照多跳的方式進(jìn)行數(shù)據(jù)的發(fā)送，并且每跳的傳輸距離假定為D。

簇內(nèi)成員節(jié)點(diǎn)離簇首的距離假設(shè)它不超過(guò)自由空間模型的臨界值，這樣，一個(gè)非簇首節(jié)點(diǎn)的能量消耗為:

如果整個(gè)簇內(nèi)節(jié)點(diǎn)的密度是均勻的，那么ρ=N1/()，那么，則

則發(fā)送一幀中整個(gè)簇的能量消耗為:

那么在R1區(qū)域的一幀的總能量消耗為:

忽略電路消耗和數(shù)據(jù)融合消耗，對(duì)Etotal求倒，讓其等于零，得到h1最優(yōu)簇頭數(shù)為:

這個(gè)最優(yōu)值和上面分區(qū)域大小的計(jì)算是在做了很多假設(shè)的情況下得到的，只能作為參考，實(shí)際的應(yīng)用中需要具體考慮和設(shè)定。

2 CHTD簇?cái)?shù)據(jù)傳輸

為了減小遠(yuǎn)距離的通信能耗，在CHTD算法的基礎(chǔ)上給出了改進(jìn)的CHTD多跳路由算法(CHTD-M)，多跳方式是在簇頭間生成一種基于距離能量代價(jià)的路由樹(shù)，簇頭選擇下一跳節(jié)點(diǎn)時(shí)，綜合考慮了兩節(jié)點(diǎn)間鏈路能耗、接收節(jié)點(diǎn)的剩余能量水平和距離基站的位置，通過(guò)局部信息動(dòng)態(tài)選擇下一跳，并且通過(guò)引入最短有效轉(zhuǎn)發(fā)距離，合理有效的選擇多跳，實(shí)驗(yàn)結(jié)果表明改進(jìn)的CHTD-M進(jìn)一步優(yōu)化了網(wǎng)絡(luò)中簇頭節(jié)點(diǎn)的能量消耗，顯著地延長(zhǎng)了網(wǎng)絡(luò)的生命周期。CHTD-M的下一跳路由節(jié)點(diǎn)在緊鄰的區(qū)域內(nèi)，簇頭節(jié)點(diǎn)和它的下一跳路由節(jié)點(diǎn)距離不超過(guò)自己的通信范圍，很容易實(shí)現(xiàn)。

2.1 最優(yōu)轉(zhuǎn)發(fā)跳數(shù)

在無(wú)線傳感器網(wǎng)絡(luò)中采用多跳的路由機(jī)制，雖然能夠降低網(wǎng)絡(luò)數(shù)據(jù)通信的能量開(kāi)銷，但當(dāng)節(jié)點(diǎn)之間的距離較近時(shí)，卻增加了作為路由中間節(jié)點(diǎn)的電路能量消耗，有時(shí)采用多跳的路由方式所消耗的能量要大于直接傳送的方式，進(jìn)而在一定的范圍內(nèi)會(huì)增加網(wǎng)絡(luò)整體的能量消耗。因此，在簇?cái)?shù)據(jù)傳輸時(shí)應(yīng)該合理的選擇多跳。假設(shè)有N個(gè)傳感器節(jié)點(diǎn)隨機(jī)分布在半徑為r的一個(gè)區(qū)域內(nèi)。區(qū)域內(nèi)的傳感器節(jié)點(diǎn)按照距離基站的遠(yuǎn)近劃分為不同的區(qū)域，分別為r1，r2，r3，r4，…，rn，如圖 1。

圖1 無(wú)線傳感器網(wǎng)絡(luò)多跳模型

在這個(gè)區(qū)域中有h個(gè)簇頭，平均分布于整個(gè)區(qū)域中，位于rn區(qū)域的簇頭節(jié)點(diǎn)和基站的通信需要rn－1區(qū)域的簇頭節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，并且每次通信的距離都不超過(guò)自由衰減模型的范圍，為了便于研究，假設(shè)每個(gè)區(qū)域的簇頭節(jié)點(diǎn)位于該區(qū)域的中部，并且每個(gè)區(qū)域的環(huán)寬度相同都為r，即r1區(qū)域的簇頭位于r/2，r2區(qū)域的簇頭位于3r/2，r2區(qū)域的簇頭節(jié)點(diǎn)向基站發(fā)送數(shù)據(jù)時(shí)，需要r1區(qū)域的簇頭節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，r3區(qū)域的簇頭向基站發(fā)送數(shù)據(jù)需要r2區(qū)域的簇頭節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)，以此類推，則當(dāng)位于ri區(qū)域的簇頭向基站發(fā)送k比特?cái)?shù)據(jù)時(shí)，網(wǎng)絡(luò)中的單個(gè)簇頭節(jié)點(diǎn)發(fā)送數(shù)據(jù)的能耗為:

其中β是數(shù)據(jù)傳輸經(jīng)過(guò)的跳數(shù)，則網(wǎng)絡(luò)的總體能量消耗為:

節(jié)省能量的跳數(shù)可從下面的計(jì)算得出:

由(7)可得:

由(8)可知，當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)距離基站的距離小于d0時(shí)，采用直接傳輸?shù)姆绞娇梢怨?jié)省網(wǎng)絡(luò)能量，當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)距離基站的距離大于d0時(shí)，采用多跳的傳輸方式更能夠節(jié)約網(wǎng)絡(luò)的能量，我們把這個(gè)值定義為節(jié)點(diǎn)的最短有效轉(zhuǎn)發(fā)距離(Restriction_distance)。從而可知，一個(gè)距離基站距離為d的傳感器簇頭節(jié)點(diǎn)i，它的節(jié)能轉(zhuǎn)發(fā)跳數(shù)βopt=「d/d0?。

在實(shí)際應(yīng)用當(dāng)中，選擇下一跳路由的轉(zhuǎn)發(fā)節(jié)點(diǎn)時(shí)，應(yīng)當(dāng)綜合考慮整個(gè)網(wǎng)絡(luò)能量平衡的因素。

2.2 簇間路由樹(shù)的生成

在網(wǎng)絡(luò)部署完畢后，基站需要用一個(gè)給定的發(fā)送功率向網(wǎng)絡(luò)內(nèi)廣播一個(gè)信號(hào)Sink_ADV，節(jié)點(diǎn)以此信號(hào)強(qiáng)度計(jì)算到基站的近似距離。獲得這個(gè)距離不但有助于節(jié)點(diǎn)在向基站傳輸數(shù)據(jù)時(shí)選擇合適的發(fā)送功率來(lái)節(jié)約能量消耗，而且它還是構(gòu)造簇間路由樹(shù)的必需信息之一。

在有些路由算法中，中繼節(jié)點(diǎn)對(duì)接收到的數(shù)據(jù)進(jìn)行數(shù)據(jù)融合，然后再斷續(xù)發(fā)送。實(shí)際上，不同簇之間的數(shù)據(jù)相關(guān)性很小［14］，因此在本文中，中繼簇頭節(jié)點(diǎn)不再對(duì)來(lái)自其它簇頭的數(shù)據(jù)進(jìn)一步融合，只是簡(jiǎn)單的轉(zhuǎn)發(fā)給下一跳。

其中，eij表示節(jié)點(diǎn)i和j直接通信的能量消耗，RSSj指節(jié)點(diǎn)j接收到Sink_ADV的信號(hào)強(qiáng)度，RSSmax是指基站廣播Sink_ADV時(shí)的信號(hào)強(qiáng)度，D()表示距離估算函數(shù)。

綜合考慮能量平衡的因素，本文節(jié)點(diǎn)i選擇節(jié)點(diǎn)j作為父節(jié)點(diǎn)的策略是選擇代價(jià)最小的DEC(i，j)，即:

若節(jié)點(diǎn)i的鄰居信息表為空，說(shuō)明此簇頭周圍沒(méi)有其它的簇頭存在，這種情況會(huì)出現(xiàn)在網(wǎng)絡(luò)運(yùn)行到后期，大部分節(jié)點(diǎn)已經(jīng)死亡的情況下，此時(shí)，簇頭將數(shù)據(jù)直接傳輸給基站。通過(guò)式(11)可以看出，DEC(i，j)充分考慮了兩節(jié)點(diǎn)間通信的能量消耗和鄰居節(jié)點(diǎn)的剩余能量以及到基站的距離狀況，通過(guò)對(duì)這3個(gè)因素的綜合考慮，選擇最小的DEC(i，j)，使得在發(fā)送能耗較小的情況下，距離基站較近并且剩余能量充足的節(jié)點(diǎn)優(yōu)先成為父節(jié)點(diǎn)。

按照以上策略確定路由方式之后，簇頭生成一棵以基站為根的樹(shù)，數(shù)據(jù)沿著基站的方向傳輸。

2.3 CHTD-M 的分析

通過(guò)分析整個(gè)算法，CHTD-M算法具有以下兩個(gè)特性:(1)算法是完全分布式的，節(jié)點(diǎn)完全依賴本地信息決定自身的狀態(tài)，無(wú)需知道其它節(jié)點(diǎn)的位置，具有良好的伸縮性。(2)算法的消息復(fù)雜度為O(N)。在整個(gè)網(wǎng)絡(luò)中，有N個(gè)節(jié)點(diǎn)參與簇頭競(jìng)選，最終共選出k個(gè)簇頭，每個(gè)簇頭廣播一條CH_ADV消息宣布其競(jìng)選成功，則它們共廣播k條CH_ADV消息，而N－k個(gè)簇成員廣播N－k條JOIN_REQ消息。因此，網(wǎng)絡(luò)中總的消息開(kāi)銷為k+N－k=N，所以消息復(fù)雜度為O(N)。該特點(diǎn)說(shuō)明算法的消息開(kāi)銷較小，能量高效。

我們引入閾值Restriction_distance，若簇頭到基站距離小于Restriction_distance，則直接與基站進(jìn)等通信。若簇頭到基站距離大于Restriction_distance時(shí)，簇頭i的路由選擇方法如下所示。

定義1通信能量消耗 任何兩個(gè)可直接通信的節(jié)點(diǎn)i、j，通信一次發(fā)送k比特?cái)?shù)據(jù)的能量消耗定義為兩點(diǎn)之間距離dij的函數(shù)eij(k，dij)，公式如下:

其中α為功耗指數(shù)，與傳輸距離有關(guān)。

定義2距離能量代價(jià) 若某個(gè)簇的當(dāng)前簇頭為i，j是i的鄰居信息表中的一個(gè)簇頭節(jié)點(diǎn)，則節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離能量代價(jià) DEC(Distance Energy Cost)定義如下:

3 仿真分析

本文為了研究在不同的范圍內(nèi) LEACH、TBLEACH、CHTD和CHTD-M的性能的差異，分別在兩個(gè)場(chǎng)景中進(jìn)行了模擬，具體見(jiàn)表1，通過(guò)仿真網(wǎng)絡(luò)的生命周期、接收數(shù)據(jù)包、能量消耗和負(fù)載均衡來(lái)觀察改進(jìn)的CHTD-M的網(wǎng)絡(luò)性能。

表1 仿真相關(guān)參數(shù)

3.1 生命周期

圖2是100 m×100 m場(chǎng)景下的 LEACH、TBLEACH、CHTD和CHTD-M算法中無(wú)線傳感器網(wǎng)絡(luò)生命周期的對(duì)比圖，在場(chǎng)景1中CHTD-M的第一個(gè)節(jié)點(diǎn)死亡的時(shí)間(FND)是LEACH的1.4倍，一半節(jié)點(diǎn)死亡(HND)的時(shí)間是LEACH的1.2倍。這表明CHTD-M算法使能量的損耗更加均勻的分布到所有節(jié)點(diǎn)中，避免了單個(gè)節(jié)點(diǎn)因能量損耗過(guò)大而過(guò)早死亡。與TB-LEACH和CHTD相比，CHTD-M算法的FND和HND時(shí)間幾乎同時(shí)提高了1.1倍左右，這是因?yàn)镃HTD-M采用了節(jié)能跳數(shù)，降低了網(wǎng)絡(luò)的整體能量消耗。

圖2 100 m×100 m死亡節(jié)點(diǎn)和輪的關(guān)系

圖3是200 m×200 m場(chǎng)景下的網(wǎng)絡(luò)生命周期，在場(chǎng)景2中CHTD-M的優(yōu)勢(shì)進(jìn)一步得到體現(xiàn)，其FND、HND 時(shí)間分別是 LEACH 的3.2 倍、1.3 倍，與TB-LEACH和CHTD相比，CHTD-M的FND時(shí)間分別提高了1.9倍和1.3倍，HND時(shí)間也幾乎同時(shí)提高了1.2倍，這是因?yàn)樵诖髨?chǎng)景環(huán)境下，其它3種算法的簇頭和基站之間的通信距離加大，簇頭單次的通信能量損耗也隨之加大，而CHTD-M中簇頭和基站之間的通信選擇通信能耗小、離基站較近且能量充裕的簇頭轉(zhuǎn)發(fā)，因此單個(gè)簇頭單輪通信能量損耗不會(huì)隨區(qū)域的增大而大幅增加，并且單輪的簇頭和基站通信的過(guò)程中，簇頭之間趨于能量平衡。另外，我們知道從FND到HND的時(shí)間跨度能夠反應(yīng)網(wǎng)絡(luò)中節(jié)點(diǎn)的能量均衡狀況，跨度越小表明網(wǎng)絡(luò)的能量使用越高效。CHTD-M不僅顯著地延長(zhǎng)了網(wǎng)絡(luò)的生命周期，而且時(shí)間跨度也較小，所以在前期，CHTDM算法的網(wǎng)絡(luò)中的存活節(jié)點(diǎn)和網(wǎng)絡(luò)覆蓋面積遠(yuǎn)遠(yuǎn)大于其它3種算法，在某個(gè)時(shí)間點(diǎn)，CHTD-M網(wǎng)絡(luò)中的節(jié)點(diǎn)開(kāi)始迅速死亡，所以后期的存活節(jié)點(diǎn)數(shù)量迅速降低，無(wú)線傳感器網(wǎng)絡(luò)中死亡節(jié)點(diǎn)的數(shù)目占有一定比例的時(shí)候我們就可以認(rèn)為網(wǎng)絡(luò)的死亡，因此，這個(gè)不影響CHTD-M在延長(zhǎng)無(wú)線傳感器網(wǎng)絡(luò)生命周期中的優(yōu)越表現(xiàn)。

圖3 200 m×200 m死亡節(jié)點(diǎn)和輪的關(guān)系

通過(guò)上述分析，我們可知，CHTD-M中的多跳策略可以節(jié)省網(wǎng)絡(luò)的通信能量消耗，相比LEACH更能夠均衡網(wǎng)絡(luò)中不同位置的簇頭節(jié)點(diǎn)的能量消耗，減少簇頭節(jié)點(diǎn)的通信能量負(fù)載，相比TB-LEACH和 CHTD，CHTD-M中的節(jié)能跳數(shù)策略能夠減少網(wǎng)絡(luò)中數(shù)據(jù)轉(zhuǎn)發(fā)的次數(shù)，能夠較小網(wǎng)絡(luò)的額外開(kāi)銷，防止網(wǎng)絡(luò)中的電路消耗過(guò)大，減弱“熱點(diǎn)問(wèn)題”對(duì)網(wǎng)絡(luò)性能的影響。

3.2 能量消耗

圖4是100 m×100 m環(huán)境下LEACH、TB-LEACH、CHTD和CHTD-M算法中網(wǎng)絡(luò)能量消耗和時(shí)間的關(guān)系，從圖中可以看出，和CHTD、TB-LEACH和LEACH相比，CHTD-M能夠節(jié)省網(wǎng)絡(luò)總體能量消耗，經(jīng)過(guò)一段時(shí)間后，LEACH的網(wǎng)絡(luò)能耗增長(zhǎng)速度緩慢，在某一時(shí)刻，CHTD-M的網(wǎng)絡(luò)總能量消耗大于LEACH，這是因?yàn)殡S著時(shí)間的推移，LEACH中的大部分節(jié)點(diǎn)已經(jīng)死亡，CHTD-M的覆蓋面積遠(yuǎn)遠(yuǎn)大于LEACH，因此網(wǎng)絡(luò)數(shù)據(jù)的采集量大于它們。

圖4 100 m×100 m環(huán)境下LEACH、TB-LEACH、CHTD、CHTD-M能量的消耗

當(dāng)網(wǎng)絡(luò)范圍變大時(shí)，CHTD-M的節(jié)能效果更加明顯，圖5是在200 m×200 m的環(huán)境下，CHTD-M和LEACH、TB-LEACH以及CHTD的能量消耗圖，從圖中可以看出，和TB-LEACH、CHTD相比，CHTD-M在時(shí)間為300輪時(shí)能夠節(jié)約LEACH將近一半的能量，同樣隨著時(shí)間的推移，CHTD-M的覆蓋面積遠(yuǎn)遠(yuǎn)大于LEACH，在某一時(shí)刻，CHTD-M的總能量消耗會(huì)大于LEACH。

圖5 200 m×200 m環(huán)境下LEACH、TB-LEACH、CHTD、CHTD-M能量的消耗

從圖4和5可知，CHTD-M采用多跳的路由策略節(jié)省了網(wǎng)絡(luò)中通信的能量消耗，和 LEACH、TBLEACH相比，它具有很明顯的節(jié)能優(yōu)勢(shì)，而CHTD隨著網(wǎng)絡(luò)范圍的逐漸變大達(dá)不到CHTD-M的良好性能。

3.3 負(fù)載均衡

無(wú)線傳感器網(wǎng)絡(luò)性能評(píng)價(jià)的重要標(biāo)準(zhǔn)之一就是網(wǎng)絡(luò)負(fù)載平衡，為了便于研究，本文將傳感器節(jié)點(diǎn)按照它與基站之間的距離等分為兩份，為了便于描述，我們假設(shè)第1份覆蓋的范圍為第1區(qū)域(距離基站較近的一半節(jié)點(diǎn))，第2份覆蓋的范圍為第2區(qū)域(距離基站較遠(yuǎn)的一半節(jié)點(diǎn))，統(tǒng)計(jì)不同算法中不同區(qū)域的節(jié)點(diǎn)能量消耗隨時(shí)間的變化狀況。

圖6為100 m×100 m環(huán)境下CHTD-M各區(qū)域能量的消耗和時(shí)間的關(guān)系，很明顯，在該場(chǎng)景下，CHTD-M中的兩個(gè)區(qū)域的能量消耗并沒(méi)有明顯的差別，其中因?yàn)榭拷镜墓?jié)點(diǎn)需要轉(zhuǎn)發(fā)來(lái)自離基站較遠(yuǎn)節(jié)點(diǎn)的數(shù)據(jù)，因此能量消耗稍微多于遠(yuǎn)離基站的區(qū)域，但是這個(gè)在可以容忍的范圍之內(nèi)，通過(guò)圖6可以看出，CHTD-M均衡了網(wǎng)絡(luò)中不同位置的節(jié)點(diǎn)的能量負(fù)載，延長(zhǎng)了網(wǎng)絡(luò)壽命。

圖6 100 m×100 m環(huán)境下CHTD-M各區(qū)能量的消耗

圖7為200 m×200 m環(huán)境下CHTD-M兩個(gè)區(qū)域的能量消耗，和100×100環(huán)境下相比，兩個(gè)區(qū)域的能量消耗差別稍大，但是，和節(jié)點(diǎn)數(shù)量增加量相比，兩個(gè)區(qū)域中單個(gè)節(jié)點(diǎn)的能量負(fù)載基本沒(méi)有太大變化，在網(wǎng)絡(luò)范圍變大的情況下，CHTD-M依然能夠使網(wǎng)絡(luò)中的節(jié)點(diǎn)負(fù)載趨于平衡，因此，和LEACH以及類似的單跳成簇算法相比，網(wǎng)絡(luò)范圍越大CHTDM的優(yōu)勢(shì)越明顯。

圖7 200 m×200 m環(huán)境下CHTD-M各區(qū)能量的消耗

綜合以上所述，通過(guò)對(duì)改進(jìn)算法進(jìn)行仿真分析，我們得到簇間多跳算法CHTD-M能夠延長(zhǎng)網(wǎng)絡(luò)的生命周期，增加網(wǎng)絡(luò)采集的數(shù)據(jù)包的數(shù)量，節(jié)省網(wǎng)絡(luò)能量消耗，均衡網(wǎng)絡(luò)的能量負(fù)載，完善了CHTD成簇算法。

4 總結(jié)

本文在對(duì)無(wú)線傳感器網(wǎng)絡(luò)路由算法深入研究的基礎(chǔ)上，總結(jié)了目前無(wú)線傳感器網(wǎng)絡(luò)路由算法研究的主要思路，分析了基于簇的無(wú)線傳感器網(wǎng)絡(luò)路由算法中存在的問(wèn)題，設(shè)計(jì)出了一種完全分布式的、能量有效的無(wú)線傳感器網(wǎng)絡(luò)分簇算法。主要進(jìn)行了如下的研究:

(1)基于無(wú)線傳感器網(wǎng)絡(luò)分簇算法研究分析的基礎(chǔ)上，給出了一種基于時(shí)間延遲機(jī)制的無(wú)線傳感器網(wǎng)絡(luò)分簇算法CHTD。該算法建立了節(jié)點(diǎn)的時(shí)間延遲機(jī)制模型并由此得到延遲時(shí)間，使得剩余能量較多的節(jié)點(diǎn)有較小的延遲時(shí)間，從而能夠在每一輪中被優(yōu)先選為簇頭，達(dá)到均衡簇頭能量消耗的目的。此外，該算法還考慮了每輪的簇頭節(jié)點(diǎn)個(gè)數(shù)以及位置分布問(wèn)題，通過(guò)維持每個(gè)節(jié)點(diǎn)的簇首信息集合使得每輪產(chǎn)生的簇頭數(shù)目穩(wěn)定且位置均勻分布。并通過(guò)仿真驗(yàn)證了CHTD分簇算法比LEACH和目前已有的基于定時(shí)器的分簇算法TB-LEACH對(duì)網(wǎng)絡(luò)性能有明顯改善。

(2)針對(duì)CHTD分簇完成之后的簇?cái)?shù)據(jù)傳輸階段進(jìn)行算法改進(jìn)，給出CHTD-M簇間多跳路由算法。該算法將網(wǎng)絡(luò)中均勻分布的簇頭構(gòu)造成一棵路由樹(shù)，通過(guò)多跳傳輸?shù)姆绞綔p少直接與基站通信的簇頭節(jié)點(diǎn)數(shù)量，從而更進(jìn)一步的降低能量開(kāi)銷。同時(shí)，該算法還限制了多跳路由的最短轉(zhuǎn)發(fā)距離，降低了中間節(jié)點(diǎn)的電路開(kāi)銷，減少了多跳的數(shù)據(jù)轉(zhuǎn)發(fā)次數(shù)，節(jié)省了網(wǎng)絡(luò)的能量消耗，弱化了網(wǎng)絡(luò)中的“熱點(diǎn)問(wèn)題”。最后對(duì)整體算法進(jìn)行仿真，實(shí)驗(yàn)結(jié)果表明，CHTD-M把節(jié)約網(wǎng)絡(luò)能量和保持網(wǎng)絡(luò)負(fù)載平衡結(jié)合起來(lái)，顯著地延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

［1］Akkaya K，Younis M.A Survey on Routing Protocols for Wireless Sensor Networks［J］.Ad Hoc Networks，2005，3(3):325－349.

［2］李建中，李金寶，石勝飛.傳感器網(wǎng)絡(luò)及其數(shù)據(jù)管理的概念、問(wèn)題與進(jìn)展［J］.軟件學(xué)報(bào)，2003，14(10):1717－1727.

［3］曹涌濤，何晨，蔣鈴鴿.無(wú)線傳感器網(wǎng)絡(luò)中基于自適應(yīng)定時(shí)器策略的分簇算法［J］.電子學(xué)報(bào)，2007，35(9):1719－1723.

［4］Hu Junping，Jin Yuhui，Dou Liang.A Time-Based Cluster-Head Selection Algorithm for LEACH［C］//13th IEEE Symposium on Computers and Communications，2008:1172－1176.

［5］Mhatre V，Rosenberg C.Design Guidelines for Wireless Sensor Networks:Communication，Clustering and Aggregation［J］.Ad Hoc Networks，2004，2(1):45－63.

［6］胡鋼，謝冬梅，吳元忠.無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議LEACH的研究與改進(jìn)［J］.傳感技術(shù)學(xué)報(bào)，2007，20(6):1391－1396.

［7］Fan Xiangning，Song Yulin.Improvement on LEACH Protocol of Wireless Sensor Networks［C］//Proceedings of 2007 International Conference on Sensor Technologies and Applications，2007:517－528.

［8］張磊，陳曙.一個(gè)新的基于能量和距離的傳感器網(wǎng)絡(luò)協(xié)議［J］.計(jì)算機(jī)應(yīng)用，2008，28(5):1117－1119.

［9］李成法，陳貴海，吳杰，等.一種基于非均勻分簇的無(wú)線傳感器網(wǎng)絡(luò)路由協(xié)議［J］.計(jì)算機(jī)學(xué)報(bào)，2007，30(1):27－36.

［10］劉志，裘正定.基于分環(huán)多跳的無(wú)線傳感器網(wǎng)絡(luò)分簇路由算法［J］.通信學(xué)報(bào)，2008，29(3):104－112.

［11］朱藝華，沈丹丹，吳萬(wàn)登，等.無(wú)線傳感器網(wǎng)絡(luò)優(yōu)化生存時(shí)間的動(dòng)態(tài)路由算法［J］.電子學(xué)報(bào)，2009，37(5):1041－1045.

［12］王寅，尚鳳軍，任東海.一種基于自適應(yīng)蟻群系統(tǒng)的傳感器網(wǎng)絡(luò) QoS 路由算法［J］.傳感技術(shù)學(xué)報(bào)，2010，23(2):239－244.

［13］Heinzelman W R，Chandrakasan A P，Balakrishnan H.An Application-Specific Protocol Architecture for Wireless Microsensor Networks［J］.IEEE Trans.on Wireless Communications，2002，1(4):660－670.

［14］Li Chengfa，Ye Mao，Chen Guihai，et al.An Energy-Efficient Unequal Clustering Mechanism for Wireless Sensor Networks［C］//IEEE International Conference on Mobile Ad-Hoc and Sensor Systems Conference，2005:604－611.