丁緒星 王婷婷 褚 浩 李 磊

(安徽師范大學(xué)物理與電子信息學(xué)院 安徽 蕪湖 241000)

一種HCTRP協(xié)議下PEGASIS最優(yōu)路徑算法

丁緒星 王婷婷 褚 浩 李 磊

(安徽師范大學(xué)物理與電子信息學(xué)院 安徽 蕪湖 241000)

WSNs區(qū)域內(nèi)節(jié)點(diǎn)隨機(jī)分布不均勻，采用HCTRP-PEGASIS路由算法建鏈時(shí)僅參考節(jié)點(diǎn)彼此之間的距離，致使部分傳感器節(jié)點(diǎn)做過多無(wú)用功，造成網(wǎng)絡(luò)能源浪費(fèi)、節(jié)點(diǎn)過早衰竭死亡。給出新算法使建鏈時(shí)除了參照節(jié)點(diǎn)彼此之間的距離，同時(shí)考慮實(shí)際傳感器通信半徑、相鄰節(jié)點(diǎn)的當(dāng)前能量、當(dāng)前節(jié)點(diǎn)密度，進(jìn)而確定下一個(gè)接替節(jié)點(diǎn)；以此類推在每個(gè)子區(qū)域內(nèi)，最終形成一條數(shù)據(jù)冗余少、能耗低的數(shù)據(jù)傳輸鏈。仿真顯示，相對(duì)于LEACH、PEGASIS、HCTRP-PEGASIS，網(wǎng)絡(luò)生存周期改進(jìn)算法提高約20%；網(wǎng)絡(luò)平均總能耗平均到每個(gè)節(jié)點(diǎn)，改進(jìn)算法至少降低9 J。故子區(qū)域內(nèi)建鏈時(shí)，結(jié)合節(jié)點(diǎn)實(shí)際通信范圍及節(jié)點(diǎn)密度等因素來(lái)選擇鏈上組員，可以進(jìn)一步降低網(wǎng)絡(luò)功耗，提高網(wǎng)絡(luò)能量利用率，并且延遲第一個(gè)節(jié)點(diǎn)死亡時(shí)間。

WSNs HCTRP協(xié)議 PEGASIS協(xié)議 路由算法

0 引 言

WSN廣泛應(yīng)用在軍事、醫(yī)療、環(huán)境監(jiān)控和行業(yè)管理等領(lǐng)域，故如何降低因傳感器節(jié)點(diǎn)自身能量以及計(jì)算和通信能力限制帶來(lái)的網(wǎng)絡(luò)的能源消耗，一直是研究的熱點(diǎn)問題[1]。在LEACH[2]協(xié)議基礎(chǔ)上，提出一種新的基于鏈(Chain)的路由算法——PEGASIS協(xié)議。其相對(duì)LEACH算法而言，可降低重構(gòu)簇的成本，并利用數(shù)據(jù)融合降低數(shù)據(jù)收發(fā)過程的頻率，有效地減少能量的消耗。

PEGASIS是一種典型鏈狀結(jié)構(gòu)路由協(xié)議[3]。該協(xié)議的中心思想：貪婪算法將網(wǎng)絡(luò)中所有節(jié)點(diǎn)構(gòu)建成一條路徑鏈，之后節(jié)點(diǎn)沿著路徑鏈將數(shù)據(jù)傳遞至基站[4-5]，如文獻(xiàn)[6]提出的PDCH協(xié)議。該協(xié)議采用雙簇頭選擇鏈樹層次結(jié)構(gòu)，使非簇頭與簇頭之間的距離最小化，避免“長(zhǎng)鏈”產(chǎn)生；同時(shí)也減少所有節(jié)點(diǎn)的數(shù)據(jù)傳輸接收次數(shù)。文獻(xiàn)[7]針對(duì)PEGASIS協(xié)議過程中的數(shù)據(jù)冗余和延遲問題，提出E-PEGASIS協(xié)議，該協(xié)議將部署子集內(nèi)的節(jié)點(diǎn)使用支配集概念來(lái)進(jìn)行激活，并因傳感器節(jié)點(diǎn)的隨機(jī)分布形成隨機(jī)的稀疏WSN網(wǎng)絡(luò)部署這一屬性，來(lái)確定目標(biāo)鏈?zhǔn)讜r(shí)，需計(jì)算節(jié)點(diǎn)的周圍節(jié)點(diǎn)與基站的接近度。E-PEGASIS協(xié)議不僅延長(zhǎng)網(wǎng)絡(luò)生命周期，同時(shí)能很好利用傳感器網(wǎng)絡(luò)部署區(qū)域的隨機(jī)覆蓋率。文獻(xiàn)[8]提出的PEGASIS改進(jìn)算法，該協(xié)議根據(jù)神經(jīng)網(wǎng)絡(luò)思想選擇鏈頭，運(yùn)用蟻群算法遵循信息素的強(qiáng)度的方法，在各子區(qū)域內(nèi)尋找最佳路徑將數(shù)據(jù)發(fā)送至基站。此方式創(chuàng)建的數(shù)據(jù)路徑鏈，致使鏈樹更分布式。繼而極大減小數(shù)據(jù)傳輸距離的總平方，乃至延長(zhǎng)網(wǎng)絡(luò)生命周期。與此同時(shí)PEGASIS改進(jìn)協(xié)議動(dòng)用最小化的傳輸距離和的平方和，來(lái)間接的反映節(jié)點(diǎn)彼此之間的距離和節(jié)點(diǎn)的剩余能量。

除了以上改進(jìn)協(xié)議，近幾年又提出了基于HCTRP協(xié)議下PEGASIS算法；如文獻(xiàn)[9-10]，該算法為預(yù)防“長(zhǎng)鏈”現(xiàn)象出現(xiàn)，先將整個(gè)區(qū)域劃分為均等的子區(qū)域，然后在各個(gè)子區(qū)域內(nèi)并行構(gòu)建多條子數(shù)據(jù)鏈，以此將整個(gè)區(qū)域覆蓋，完成數(shù)據(jù)匯集任務(wù)。是以用“化整為零”的思路既減少數(shù)據(jù)鏈的長(zhǎng)度，又降低出現(xiàn)“長(zhǎng)鏈”機(jī)率。不過綜上分析發(fā)現(xiàn)提出的大多數(shù)優(yōu)化PEGASIS協(xié)議都未注意以下問題[11]：

1) 比擬位于基站近的孤獨(dú)節(jié)點(diǎn)，距離遠(yuǎn)的孤獨(dú)節(jié)點(diǎn)與BS通信，需要消耗更多的能量。

2) 均在節(jié)點(diǎn)隨機(jī)均勻分布的情況下，運(yùn)用方法來(lái)進(jìn)一步提升網(wǎng)絡(luò)生命周期以及減少網(wǎng)絡(luò)功耗，而未研究網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)分布不均勻情況下算法的適應(yīng)性。

依據(jù)以上問題以及更大程度上防止“長(zhǎng)鏈”、減少數(shù)據(jù)傳輸過程中傳輸次數(shù)，本文在基于HCTRP協(xié)議的PEGASIS算法基礎(chǔ)上深化研究。本文算法為建設(shè)最優(yōu)數(shù)據(jù)傳輸路徑，遴選鏈上成員不僅考慮節(jié)點(diǎn)彼此之間的距離，而且還有節(jié)點(diǎn)剩余能量、周邊節(jié)點(diǎn)密度、節(jié)點(diǎn)通信半徑等因素。如此在節(jié)點(diǎn)隨機(jī)不均勻分布境況(特別是節(jié)點(diǎn)密集區(qū)域)建鏈時(shí)，通過探尋出一條最優(yōu)路徑鏈，解決建鏈過程中部分節(jié)點(diǎn)做過多無(wú)用功以及數(shù)據(jù)傳輸路徑鏈迂回復(fù)雜等問題。

1 HCTRP-PEGASIS協(xié)議

在PEGASIS基礎(chǔ)上，提出的HCTRP-PEGA-SIS路由算法[12]。該算法包括兩個(gè)階段，即節(jié)點(diǎn)區(qū)域劃分階段和節(jié)點(diǎn)建鏈及數(shù)據(jù)傳輸階段。HCTRP-PEGASIS算法網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。

圖1 HCTRP-PEGASIS算法

1.1 節(jié)點(diǎn)區(qū)域劃分階段

在系統(tǒng)初始化階段，根據(jù)基站BS劃分區(qū)域有很多方式。例如根據(jù)節(jié)點(diǎn)與BS的距離，將整個(gè)區(qū)域分為逐次疊加同心圓子區(qū)域，節(jié)點(diǎn)隨機(jī)分布在各個(gè)層次里。如圖1(a),而每個(gè)子區(qū)域內(nèi)節(jié)點(diǎn)分布密度等其他參數(shù)可由BS根據(jù)實(shí)際情況(例如節(jié)點(diǎn)數(shù)量，區(qū)域大小等)確定。

1.2 節(jié)點(diǎn)建鏈階段

子區(qū)域劃分好后，經(jīng)過節(jié)點(diǎn)建鏈階段后形成的鏈樹如圖1(b)所示，以某一子區(qū)域?yàn)槔?，建鏈過程如下：

1) 選出該子區(qū)域里距離BS最遠(yuǎn)的節(jié)點(diǎn)定為根節(jié)點(diǎn)，隨即從根節(jié)點(diǎn)開始建鏈。

2) 計(jì)算根節(jié)點(diǎn)與附近所有鄰居節(jié)點(diǎn)之間的距離，記為di。

3) 將其中最小值di所對(duì)應(yīng)的neighbor定為鏈上承接節(jié)點(diǎn)；循環(huán)2)和3)直到建鏈傳承到領(lǐng)導(dǎo)節(jié)點(diǎn)，進(jìn)行4)。

4) 領(lǐng)導(dǎo)節(jié)點(diǎn)則將整個(gè)鏈上的數(shù)據(jù)接收并融合后Broadcast給BS。

5) 確立孤獨(dú)節(jié)點(diǎn)(未當(dāng)選為鏈上成員節(jié)點(diǎn))，使孤獨(dú)節(jié)點(diǎn)直接與BS通信。

1.3 能耗模型

承接節(jié)點(diǎn)接收上一節(jié)點(diǎn)采集的數(shù)據(jù)以及將自身采集的數(shù)據(jù)與接收數(shù)據(jù)融合后傳遞給下一承接節(jié)點(diǎn)都須要消耗一定的能量，故在這個(gè)過程應(yīng)用能耗模型為：在無(wú)線通信電路發(fā)送和接收一字節(jié)的能量消耗分別為Et和Er，而Et和Er計(jì)算如式(1)和式(2)所示。

Et=α+λ×dn

(1)

Er=β

(2)

式(1)和式(2)中參數(shù)具體數(shù)值如表1。假設(shè)節(jié)點(diǎn)a向節(jié)點(diǎn)b發(fā)送m bit數(shù)據(jù)包，b將自己的數(shù)據(jù)與mbit的數(shù)據(jù)包融合后，向節(jié)點(diǎn)c發(fā)送的是一個(gè)Mbit數(shù)據(jù)包。在這個(gè)過程a發(fā)送數(shù)據(jù)包消耗的能量則為m×Et，b接收數(shù)據(jù)包消耗的能量則為m×Er。

表1 參數(shù)設(shè)置

2 HCTRP-PEGASIS改進(jìn)協(xié)議

HCTRP-PEGASIS算法建鏈過程是在傳感器節(jié)點(diǎn)密度均勻隨機(jī)分布情景下實(shí)行，然而實(shí)際WSN應(yīng)用環(huán)境，傳感器節(jié)點(diǎn)是隨機(jī)不均勻分布(可能某些區(qū)域傳感器節(jié)點(diǎn)分布得比較密集)，便意味著某區(qū)域因分布過多節(jié)點(diǎn)，致使部分傳感器節(jié)點(diǎn)復(fù)式采擷已有數(shù)據(jù)，導(dǎo)致網(wǎng)絡(luò)資源浪費(fèi)。同時(shí)也容易形成曲折復(fù)雜的“長(zhǎng)鏈”，增加整個(gè)網(wǎng)絡(luò)功耗。是以本文根據(jù)傳感器實(shí)際通信半徑對(duì)HCTRT—PEGASI-S協(xié)議作進(jìn)一步的優(yōu)化。

本文算法是在節(jié)點(diǎn)建鏈階段作出改進(jìn)，關(guān)于各子區(qū)域內(nèi)的節(jié)點(diǎn)，不是直接使用貪婪算法將各子區(qū)域內(nèi)所有節(jié)點(diǎn)盡可能都選用為鏈上組員，而是綜合考慮預(yù)選節(jié)點(diǎn)的剩余能量、預(yù)選節(jié)點(diǎn)與上一承接節(jié)點(diǎn)之間的距離、預(yù)選節(jié)點(diǎn)周圍節(jié)點(diǎn)分布密度以及節(jié)點(diǎn)通信半徑等因素，來(lái)挑選鏈上成員節(jié)點(diǎn)。如此在各子區(qū)域即確立一條最優(yōu)數(shù)據(jù)傳輸路徑鏈。

2.1 傳感器網(wǎng)絡(luò)模型

創(chuàng)建一個(gè)由N個(gè)傳感器節(jié)點(diǎn)組成的WSN網(wǎng)絡(luò)，該網(wǎng)絡(luò)應(yīng)用環(huán)境為周期性的數(shù)據(jù)收集，并基于以下假設(shè)：

(1) 基站BS節(jié)點(diǎn)固定設(shè)立在測(cè)試區(qū)域的中心位置。

(2) 所有節(jié)點(diǎn)完全相同，隨機(jī)不均勻散布于網(wǎng)絡(luò)區(qū)域內(nèi)；每個(gè)節(jié)點(diǎn)不僅可以和網(wǎng)絡(luò)中其余任何節(jié)點(diǎn)相互通信，也可以直接與BS節(jié)點(diǎn)通信。

(3) 節(jié)點(diǎn)能量有限且初始能量相同。

(4) 信道對(duì)稱且無(wú)線電信號(hào)在各個(gè)方向上能耗相同。

(5) 節(jié)點(diǎn)傳輸數(shù)據(jù)消耗的能量取決于傳輸離。

2.2 算法過程

2.2.1 改進(jìn)算法主鏈處理方式

本文改進(jìn)算法節(jié)點(diǎn)區(qū)域劃分方式：BS放置在坐標(biāo)原點(diǎn)且每象限均二等分，如此將整個(gè)網(wǎng)絡(luò)平均劃分為八個(gè)子區(qū)域。每個(gè)子區(qū)域內(nèi)，首先將距離基站BS最遠(yuǎn)的節(jié)點(diǎn)設(shè)置為開始節(jié)點(diǎn)(Startnode)，距離BS最近的節(jié)點(diǎn)設(shè)置為領(lǐng)導(dǎo)節(jié)點(diǎn)(Leadnode)。然后Startnode參考傳感器實(shí)際通信半徑D，則會(huì)在通信D范圍外的繁多節(jié)點(diǎn)來(lái)選擇承接節(jié)點(diǎn)；再綜合考慮預(yù)選節(jié)點(diǎn)的當(dāng)前能量、周圍預(yù)選節(jié)點(diǎn)數(shù)目、Startnode與預(yù)選節(jié)點(diǎn)之間距離。現(xiàn)為說明方便將這些因素借用參數(shù)Edist表示，則參數(shù)須滿足式(3)比例關(guān)系。

最后，Startnode再依據(jù)式(3)計(jì)算參數(shù)Edist，挑選鏈上下一承接節(jié)點(diǎn)，Edist計(jì)算如公式：

Edist=(dmax/d)+(Eroot/Einit)

(3)

其中dmax為網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間最遠(yuǎn)的距離。Eroot為預(yù)選節(jié)點(diǎn)的當(dāng)前能量，Einit為節(jié)點(diǎn)的初始能量且為固定值。計(jì)算Startnode與附近所有預(yù)選節(jié)點(diǎn)的Edist值，最終確定最大值Edist所對(duì)應(yīng)的節(jié)點(diǎn)成為鏈上成員。隨之承接節(jié)點(diǎn)重復(fù)以上工作，直到承接到Leadnode，則主鏈路徑創(chuàng)建完畢。其具體流程如圖2所示。

圖2 構(gòu)建主鏈流程圖

2.2.2 改進(jìn)算法孤獨(dú)節(jié)點(diǎn)通信方式

HCTRP-PEGASIS協(xié)議中孤獨(dú)節(jié)點(diǎn)是與BS節(jié)點(diǎn)直接通信，以致部分孤獨(dú)節(jié)點(diǎn)傳送數(shù)據(jù)，因距離BS節(jié)點(diǎn)耗費(fèi)大量能量而過早死亡。為延長(zhǎng)孤獨(dú)節(jié)點(diǎn)壽命，本文算法改進(jìn)方式：將孤獨(dú)節(jié)點(diǎn)直接與周圍已創(chuàng)建的某條數(shù)據(jù)路徑鏈上的某個(gè)節(jié)點(diǎn)進(jìn)行通信。孤獨(dú)節(jié)點(diǎn)同樣根據(jù)與附近所有數(shù)據(jù)鏈上節(jié)點(diǎn)的距離以及鏈上節(jié)點(diǎn)的當(dāng)前能量，來(lái)選擇中繼節(jié)點(diǎn)。為方便計(jì)算現(xiàn)用參數(shù)edist來(lái)表示，edist計(jì)算如公式：

edist=(d/dmax)+(einit/eclust)

(4)

其中dmax為網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間最遠(yuǎn)的距離，einit為所選鏈上某節(jié)點(diǎn)的當(dāng)前能量，einit為節(jié)點(diǎn)的初始能量且為固定值。

孤獨(dú)節(jié)點(diǎn)通信方式如流程圖3所示。孤獨(dú)節(jié)點(diǎn)按照此方式間接與BS節(jié)點(diǎn)通信，使其降低能量消耗、通信省時(shí)便利。

圖3 孤獨(dú)節(jié)點(diǎn)流程圖

3 仿真結(jié)果及分析

本文采用Atos-SensorSim仿真平臺(tái)，將LEACH、PEGASIS、HCTRP-PEGASIS算法、 HCTRP-PEGASIS改進(jìn)算法,分別在100 m×100 m網(wǎng)絡(luò)環(huán)境下進(jìn)行仿真。若節(jié)點(diǎn)能量小于1 J時(shí)，則判定節(jié)點(diǎn)死亡，且以后不再補(bǔ)充新的節(jié)點(diǎn)。其他具體實(shí)驗(yàn)參數(shù)如表2所示。

表2 參數(shù)設(shè)置

將200個(gè)傳感器節(jié)點(diǎn)隨機(jī)不均勻地散布在100 m×100 m的區(qū)域內(nèi)，在系統(tǒng)初始化初階，區(qū)域劃分后在第三象限隨機(jī)節(jié)點(diǎn)分布90個(gè)，第四象限節(jié)點(diǎn)隨機(jī)分布60個(gè)，其他兩個(gè)象限各隨機(jī)分布25個(gè)節(jié)點(diǎn)，如圖4所示。

圖4 100 m×100 m的區(qū)域劃分

圖5為HCTRP-PEGASIS協(xié)議仿真結(jié)果。從圖5中直觀觀察出，每一區(qū)域內(nèi)從最遠(yuǎn)節(jié)點(diǎn)開始建鏈，之后直接選擇其最近的節(jié)點(diǎn)作為下一承接節(jié)點(diǎn)，直至將該子區(qū)域內(nèi)的所有節(jié)點(diǎn)連貫為一條數(shù)據(jù)傳輸鏈。確定承接節(jié)點(diǎn)時(shí)，子區(qū)域內(nèi)的數(shù)據(jù)同步經(jīng)由開始節(jié)點(diǎn)逐層向內(nèi)傳遞至領(lǐng)導(dǎo)節(jié)點(diǎn)，最終領(lǐng)導(dǎo)節(jié)點(diǎn)將該區(qū)域內(nèi)全部數(shù)據(jù)接收融合后傳遞給基站BS。

圖5 HCTRP-PEGASIS算法

圖6是HCTRP-PEGASIS算法孤獨(dú)節(jié)點(diǎn)通信方式的仿真結(jié)果，從圖6中我們看到距離基站很遠(yuǎn)的孤獨(dú)節(jié)點(diǎn)，依舊采用與BS直接通信的話，孤獨(dú)節(jié)點(diǎn)則會(huì)大量消耗自身能量，如此縮短了節(jié)點(diǎn)的存活周期。綜合圖5和圖6的仿真結(jié)果可知，HCTRP-PEGASIS算法盡管在一定程度上避免出現(xiàn)“長(zhǎng)鏈”以及減小時(shí)間延遲。但是若某區(qū)域節(jié)點(diǎn)分布較密集的話，不僅“長(zhǎng)鏈”現(xiàn)象如故，而且數(shù)據(jù)傳輸路徑鏈迂回彎曲復(fù)雜。如此因部分節(jié)點(diǎn)重復(fù)采集數(shù)據(jù)造成數(shù)據(jù)冗長(zhǎng)多余。

圖6 HCTRP-PEGASIS協(xié)議孤獨(dú)節(jié)點(diǎn)通信方式

圖7為本文改進(jìn)算法的仿真結(jié)果。從圖中可以得出，在每一子區(qū)域內(nèi)從最遠(yuǎn)節(jié)點(diǎn)(Startnode)建鏈；開始節(jié)點(diǎn)根據(jù)參數(shù)D和式(3)確定下一承接節(jié)點(diǎn)。當(dāng)承接節(jié)點(diǎn)確定后，則升級(jí)為新的Startnode后，然后繼續(xù)根據(jù)參數(shù)D和Edist挑選新的承接節(jié)點(diǎn)；是以在各子區(qū)域內(nèi)構(gòu)建一條最優(yōu)數(shù)據(jù)路徑鏈。這樣節(jié)點(diǎn)采集的數(shù)據(jù)則沿著路徑鏈傳輸直至領(lǐng)導(dǎo)節(jié)點(diǎn)，之后經(jīng)由領(lǐng)導(dǎo)節(jié)點(diǎn)融合傳輸至BS。由圖7我們可以看出，改進(jìn)協(xié)議特別是在節(jié)點(diǎn)密集處，僅從星羅棋布的節(jié)點(diǎn)里抉擇其中能量大且與上一個(gè)承接節(jié)點(diǎn)距離適中的節(jié)點(diǎn)作為該鏈下一承接節(jié)點(diǎn)，進(jìn)而極大程度減少鏈的蜿蜒曲折和復(fù)雜度。

圖7 HCTRP-PEGASIS改進(jìn)算法

圖8是HCTRP-PEGASIS改進(jìn)協(xié)議孤獨(dú)節(jié)點(diǎn)通信方式的仿真結(jié)果。從周圍已創(chuàng)建的數(shù)據(jù)鏈根據(jù)式(4)從鏈上選擇一節(jié)點(diǎn)，該節(jié)點(diǎn)不僅距離孤獨(dú)節(jié)點(diǎn)近而且剩余能量大，孤獨(dú)節(jié)點(diǎn)直接將采集的數(shù)據(jù)傳送給該節(jié)點(diǎn)，然后經(jīng)由該節(jié)點(diǎn)所在的數(shù)據(jù)鏈傳輸至BS，以此方式改進(jìn)孤獨(dú)節(jié)點(diǎn)的通信方式。

圖8 HCTRP-PEGASIS改進(jìn)算法孤獨(dú)節(jié)點(diǎn)

現(xiàn)我們從網(wǎng)絡(luò)生命周期和網(wǎng)絡(luò)消耗兩個(gè)方面，分析比較LEACH、PEGASIS、HCTRP-PE-GASIS協(xié)議、HCTRP-PEGASIS改進(jìn)協(xié)議的性能指標(biāo)。

從圖9觀察出，HCTRP-PEGASIS改進(jìn)協(xié)議相比較HCTRP-PEGASIS協(xié)議、LEACH協(xié)議，很大程度上延長(zhǎng)第一個(gè)節(jié)點(diǎn)死亡時(shí)間。相比較LEACH協(xié)議，本文改進(jìn)算法延長(zhǎng)近似45輪；相比較HCTRP-PEGASIS協(xié)議，本文改進(jìn)協(xié)議延長(zhǎng)近似30輪。若定義網(wǎng)絡(luò)中最后一個(gè)節(jié)點(diǎn)死亡的輪數(shù)為網(wǎng)絡(luò)生命周期，由圖7可觀察出HCTRP-PEGASIS改進(jìn)協(xié)議最后一個(gè)節(jié)點(diǎn)死亡時(shí)所運(yùn)行的輪數(shù)達(dá)95輪，而HCTRP-PEGASIS協(xié)議最后一個(gè)節(jié)點(diǎn)死亡時(shí)的網(wǎng)絡(luò)生命周期輪數(shù)約為75輪，故在節(jié)點(diǎn)隨機(jī)分布不均勻WSN網(wǎng)絡(luò)下，HCTRP-PEGASIS改進(jìn)協(xié)議比HCTRP-PEGASIS算法的生存周期提高了至少20%。

圖9 節(jié)點(diǎn)存活對(duì)比圖

LEACH、PEGASIS協(xié)議、HCTRP-PEGASIS協(xié)議、優(yōu)化HCTRP-PEGASIS協(xié)議四種算法的網(wǎng)絡(luò)能耗統(tǒng)計(jì)圖如圖10所示。由圖10可觀察出在整個(gè)過程中，四種協(xié)議的網(wǎng)絡(luò)總能耗隨著時(shí)間的推移，均是逐步增加，不過HCTRP-PEGASIS改進(jìn)協(xié)議的網(wǎng)絡(luò)總能耗低于其他三種協(xié)議的網(wǎng)絡(luò)總能耗。PEGASIS協(xié)議和HCTRP-PEGASIS協(xié)議網(wǎng)絡(luò)能耗基本相同，前20輪HCTRP-PEGASIS改進(jìn)算法與LEACH兩者的網(wǎng)絡(luò)能耗相差甚微，但是20輪到50輪，HCTRP-PEGASIS改進(jìn)算法對(duì)比LEACH，平均降低總能耗平均到每個(gè)節(jié)點(diǎn)可以降低能耗至少32 J。對(duì)比PEGASIS協(xié)議和HCTRP-P-EGASIS協(xié)議，前45輪HCTRP-PEGASIS改進(jìn)算法平均降低總能耗平均到每個(gè)節(jié)點(diǎn)可以降低能耗100 J。因此在網(wǎng)絡(luò)節(jié)點(diǎn)隨機(jī)不均勻分布的環(huán)境中，按HCTRP-PEGASIS優(yōu)化算法所建的數(shù)據(jù)傳輸鏈樹，不僅降低整個(gè)網(wǎng)絡(luò)功耗，而且合理利用網(wǎng)絡(luò)資源，并延長(zhǎng)網(wǎng)絡(luò)的生命周期及進(jìn)一步減少時(shí)間延遲。

圖10 能量消耗對(duì)比圖

4 結(jié) 語(yǔ)

HCTRP-PEGASIS路由協(xié)議在節(jié)點(diǎn)稠密區(qū)域建鏈仍然會(huì)產(chǎn)生“長(zhǎng)鏈”以及部分節(jié)點(diǎn)未被合理利用，導(dǎo)致網(wǎng)絡(luò)能耗大及網(wǎng)絡(luò)資源的浪費(fèi)。針對(duì)以上問題，將HCTRP-PEGASIS協(xié)議節(jié)點(diǎn)建鏈方式作出改進(jìn)。其優(yōu)化建鏈的思路：每一周期內(nèi)為開拓最優(yōu)數(shù)據(jù)路徑鏈，挑選鏈上成員節(jié)點(diǎn)時(shí)，不僅考慮預(yù)選節(jié)點(diǎn)與開始節(jié)點(diǎn)的距離，同時(shí)考慮預(yù)選節(jié)點(diǎn)的當(dāng)前能量及周圍預(yù)選節(jié)點(diǎn)數(shù)目，來(lái)確立每一個(gè)承接節(jié)點(diǎn)，進(jìn)而動(dòng)態(tài)構(gòu)建數(shù)據(jù)鏈。相應(yīng)地也進(jìn)一步改進(jìn)了孤獨(dú)節(jié)點(diǎn)通信方式。從網(wǎng)絡(luò)消耗和網(wǎng)絡(luò)生命周期兩個(gè)方面，本文提出的基于HCTRP協(xié)議下的PEGASIS優(yōu)化路由算法優(yōu)于經(jīng)典的LEACH 協(xié)議、PEGASIS協(xié)議、HCTRP-PEGASIS協(xié)議。

本文提出的HCTRP-PEGASIS改進(jìn)協(xié)議雖然延長(zhǎng)了網(wǎng)絡(luò)的壽命，但是其壽命時(shí)間有待延長(zhǎng)。今后需要繼續(xù)優(yōu)化該算法的主鏈建鏈方式和孤獨(dú)節(jié)點(diǎn)的通信方式(著重研究孤獨(dú)節(jié)點(diǎn)的通信方式)，使之具有更長(zhǎng)的網(wǎng)絡(luò)生命周期。

[1] Guo W,Zhang W,Lu G.PEGASIS Protocol in Wireless Sensor Network Based on an Improved Ant Colony Algorithm[C]//Second International Workshop on Education Technology and Computer Science.IEEE Computer Society,2010:64-67.

[2] Sony C T,Sangeetha C P,Suriyakala C D.Multi-hop LEACH protocol with modified cluster head selection and TDMA schedule for wireless sensor networks[C]//Communication Technologies.IEEE,2015:539-543.

[3] Lindsey S,Raghavendra C S.PEGASIS:Power-efficient gathering in sensor information systems[C]//Aerospace Conference Proceedings.IEEE,2003,3:3-1125-3-1130.

[4] Yong-Chang Y U,Wei G.An Improved PEGASIS Algorithm in Wireless Sensor Network[J].Acta Electronica Sinica,2008,36(7):1309-1313.

[5] Gupta M,Saraswat L.Energy aware data collection in wireless sensor network using chain based PEGASIS[C]//Recent Advances and Innovations in Engineering (ICRAIE),2014.IEEE,2014:1-5.

[6] Wang L,Bi W,Cai Z,et al.Improved Algorithm Of Pegasis Protocol Introducing Double Cluster Heads In Wireless Sensor Network[C]//Computer,Mechatronics,Control and Electronic Engineering (CMCE),2010 International Conference on,2010:148-151.

[7] Ghosh S,Mondal S,Biswas U.Enhanced PEGASIS using ant colony optimization for data gathering in WSN[C]//International Conference on Information Communication and Embedded Systems,2016:1-6.

[8] Li T,Feng R,Fan Z,et al.An Improved PEGASIS Protocol for Wireless Sensor Network[C]//International Conference on Computer and Computing Science.IEEE Computer Society,2015:16-19.

[9] Chen Y L,Wang N C,Chen C L,et al.A Coverage Algorithm to Improve the Performance of PEGASIS in Wireless Sensor Networks[C]//Acis International Conference on Software Engineering,Artificial Intelligence,NETWORKING and Parallel/distributed Computing.IEEE,2011:123-127.

[10] Jin Wang,Jiayi Cao,Yiquan Cao,et al.An Improved Energy-Efficient Clustering Algorithm Based on MECA and PEGASIS for WSNs[C]//Third International Conference on Advanced Cloud and Big Data.IEEE Computer Society,2015:262-266.

[11] Mishra A K,Rahman R U,Bharadwaj R,et al.An enhancement of PEGASIS protocol with improved network lifetime for Wireless Sensor Networks[C]//Power Communication and Information Technology Conference.IEEE,2016:142-147.

[12] Jung S M,Han Y J,Chung T M.The Concentric Clustering Scheme for Efficient Energy Consumption in the PEGASIS[C]//The International Conference on Advanced Communication Technology.IEEE,2007:260-265.

ANOPTIMALPATHALGORITHMUNDERHIERARCHICALCHAIN-TREEROUTINGPROTOCOLBASEDONPEGASIS

Ding Xuxing Wang Tingting Chu Hao Li Lei

(CollegeofPhysicsandElectronicInformation,AnhuiNormalUniversity,Wuhu241000,Anhui,China)

In WSNs, the nodes have uneven distribution. When the hierarchical chain-tree routing protocol based on PEGASIS is used to build the chain, only the distance between nodes is referred to each other. Resulting in some of the sensor nodes do too much power, resulting in waste of network energy, node premature failure of death. In addition to the distance between the nodes, our approach also considered the actual sensor communication radius, the adjacent node’s current energy, the current node density, so as to determine the next successor node. By analogy, a data transmission chain with less data redundancy and low energy consumption was developed in each sub region. The simulation results showed that the proposed algorithm improved by about 20% in network lifetime and could reduce energy consumption of network among each node by at least 9 J compared with LEACH, PEGASIS, HCTRP-PEGASIS. Therefore, it is possible to reduce the network power consumption, enhance the energy efficiency and delay the first nodes death time by combining the node’s actual communication range and node density when the sub region is built into the chain.

WSNs HCTRP protocol PEGASIS protocol Routing Algorithm

TP393.04

A

10.3969/j.issn.1000-386x.2017.10.030

2016-10-28。國(guó)家自然科學(xué)基金項(xiàng)目(61401004)；安徽師范大學(xué)創(chuàng)新基金項(xiàng)目(2015cxsj121)。丁緒星，教授，主研領(lǐng)域：物聯(lián)網(wǎng)技術(shù)，汽車電子與數(shù)字信號(hào)處理。王婷婷，碩士生。褚浩，碩士生。李磊，碩士生。