一種HCTRP協議下PEGASIS最優路徑算法

丁緒星 王婷婷 褚 浩 李 磊

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

一種HCTRP協議下PEGASIS最優路徑算法

丁緒星 王婷婷 褚 浩 李 磊

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

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

WSNs HCTRP協議 PEGASIS協議 路由算法

0 引 言

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

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

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

1) 比擬位于基站近的孤獨節點，距離遠的孤獨節點與BS通信，需要消耗更多的能量。

2) 均在節點隨機均勻分布的情況下，運用方法來進一步提升網絡生命周期以及減少網絡功耗，而未研究網絡節點隨機分布不均勻情況下算法的適應性。

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

1 HCTRP-PEGASIS協議

在PEGASIS基礎上，提出的HCTRP-PEGA-SIS路由算法[12]。該算法包括兩個階段，即節點區域劃分階段和節點建鏈及數據傳輸階段。HCTRP-PEGASIS算法網絡結構如圖1所示。

圖1 HCTRP-PEGASIS算法

1.1 節點區域劃分階段

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

1.2 節點建鏈階段

子區域劃分好后，經過節點建鏈階段后形成的鏈樹如圖1(b)所示，以某一子區域為例，建鏈過程如下：

1) 選出該子區域里距離BS最遠的節點定為根節點，隨即從根節點開始建鏈。

2) 計算根節點與附近所有鄰居節點之間的距離，記為di。

3) 將其中最小值di所對應的neighbor定為鏈上承接節點；循環2)和3)直到建鏈傳承到領導節點，進行4)。

4) 領導節點則將整個鏈上的數據接收并融合后Broadcast給BS。

5) 確立孤獨節點(未當選為鏈上成員節點)，使孤獨節點直接與BS通信。

1.3 能耗模型

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

Et=α+λ×dn

(1)

Er=β

(2)

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

表1 參數設置

2 HCTRP-PEGASIS改進協議

HCTRP-PEGASIS算法建鏈過程是在傳感器節點密度均勻隨機分布情景下實行，然而實際WSN應用環境，傳感器節點是隨機不均勻分布(可能某些區域傳感器節點分布得比較密集)，便意味著某區域因分布過多節點，致使部分傳感器節點復式采擷已有數據，導致網絡資源浪費。同時也容易形成曲折復雜的“長鏈”，增加整個網絡功耗。是以本文根據傳感器實際通信半徑對HCTRT—PEGASI-S協議作進一步的優化。

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

2.1 傳感器網絡模型

創建一個由N個傳感器節點組成的WSN網絡，該網絡應用環境為周期性的數據收集，并基于以下假設：

(1) 基站BS節點固定設立在測試區域的中心位置。

(2) 所有節點完全相同，隨機不均勻散布于網絡區域內；每個節點不僅可以和網絡中其余任何節點相互通信，也可以直接與BS節點通信。

(3) 節點能量有限且初始能量相同。

(4) 信道對稱且無線電信號在各個方向上能耗相同。

(5) 節點傳輸數據消耗的能量取決于傳輸離。

2.2 算法過程

2.2.1 改進算法主鏈處理方式

本文改進算法節點區域劃分方式：BS放置在坐標原點且每象限均二等分，如此將整個網絡平均劃分為八個子區域。每個子區域內，首先將距離基站BS最遠的節點設置為開始節點(Startnode)，距離BS最近的節點設置為領導節點(Leadnode)。然后Startnode參考傳感器實際通信半徑D，則會在通信D范圍外的繁多節點來選擇承接節點；再綜合考慮預選節點的當前能量、周圍預選節點數目、Startnode與預選節點之間距離。現為說明方便將這些因素借用參數Edist表示，則參數須滿足式(3)比例關系。

最后，Startnode再依據式(3)計算參數Edist，挑選鏈上下一承接節點，Edist計算如公式：

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

(3)

其中dmax為網絡中任意兩個節點之間最遠的距離。Eroot為預選節點的當前能量，Einit為節點的初始能量且為固定值。計算Startnode與附近所有預選節點的Edist值，最終確定最大值Edist所對應的節點成為鏈上成員。隨之承接節點重復以上工作，直到承接到Leadnode，則主鏈路徑創建完畢。其具體流程如圖2所示。

圖2 構建主鏈流程圖

2.2.2 改進算法孤獨節點通信方式

HCTRP-PEGASIS協議中孤獨節點是與BS節點直接通信，以致部分孤獨節點傳送數據，因距離BS節點耗費大量能量而過早死亡。為延長孤獨節點壽命，本文算法改進方式：將孤獨節點直接與周圍已創建的某條數據路徑鏈上的某個節點進行通信。孤獨節點同樣根據與附近所有數據鏈上節點的距離以及鏈上節點的當前能量，來選擇中繼節點。為方便計算現用參數edist來表示，edist計算如公式：

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

(4)

其中dmax為網絡中任意兩個節點之間最遠的距離，einit為所選鏈上某節點的當前能量，einit為節點的初始能量且為固定值。

孤獨節點通信方式如流程圖3所示。孤獨節點按照此方式間接與BS節點通信，使其降低能量消耗、通信省時便利。

圖3 孤獨節點流程圖

3 仿真結果及分析

本文采用Atos-SensorSim仿真平臺，將LEACH、PEGASIS、HCTRP-PEGASIS算法、 HCTRP-PEGASIS改進算法,分別在100 m×100 m網絡環境下進行仿真。若節點能量小于1 J時，則判定節點死亡，且以后不再補充新的節點。其他具體實驗參數如表2所示。

表2 參數設置

將200個傳感器節點隨機不均勻地散布在100 m×100 m的區域內，在系統初始化初階，區域劃分后在第三象限隨機節點分布90個，第四象限節點隨機分布60個，其他兩個象限各隨機分布25個節點，如圖4所示。

圖4 100 m×100 m的區域劃分

圖5為HCTRP-PEGASIS協議仿真結果。從圖5中直觀觀察出，每一區域內從最遠節點開始建鏈，之后直接選擇其最近的節點作為下一承接節點，直至將該子區域內的所有節點連貫為一條數據傳輸鏈。確定承接節點時，子區域內的數據同步經由開始節點逐層向內傳遞至領導節點，最終領導節點將該區域內全部數據接收融合后傳遞給基站BS。

圖5 HCTRP-PEGASIS算法

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

圖6 HCTRP-PEGASIS協議孤獨節點通信方式

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

圖7 HCTRP-PEGASIS改進算法

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

圖8 HCTRP-PEGASIS改進算法孤獨節點

現我們從網絡生命周期和網絡消耗兩個方面，分析比較LEACH、PEGASIS、HCTRP-PE-GASIS協議、HCTRP-PEGASIS改進協議的性能指標。

從圖9觀察出，HCTRP-PEGASIS改進協議相比較HCTRP-PEGASIS協議、LEACH協議，很大程度上延長第一個節點死亡時間。相比較LEACH協議，本文改進算法延長近似45輪；相比較HCTRP-PEGASIS協議，本文改進協議延長近似30輪。若定義網絡中最后一個節點死亡的輪數為網絡生命周期，由圖7可觀察出HCTRP-PEGASIS改進協議最后一個節點死亡時所運行的輪數達95輪，而HCTRP-PEGASIS協議最后一個節點死亡時的網絡生命周期輪數約為75輪，故在節點隨機分布不均勻WSN網絡下，HCTRP-PEGASIS改進協議比HCTRP-PEGASIS算法的生存周期提高了至少20%。

圖9 節點存活對比圖

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

圖10 能量消耗對比圖

4 結 語

HCTRP-PEGASIS路由協議在節點稠密區域建鏈仍然會產生“長鏈”以及部分節點未被合理利用，導致網絡能耗大及網絡資源的浪費。針對以上問題，將HCTRP-PEGASIS協議節點建鏈方式作出改進。其優化建鏈的思路：每一周期內為開拓最優數據路徑鏈，挑選鏈上成員節點時，不僅考慮預選節點與開始節點的距離，同時考慮預選節點的當前能量及周圍預選節點數目，來確立每一個承接節點，進而動態構建數據鏈。相應地也進一步改進了孤獨節點通信方式。從網絡消耗和網絡生命周期兩個方面，本文提出的基于HCTRP協議下的PEGASIS優化路由算法優于經典的LEACH 協議、PEGASIS協議、HCTRP-PEGASIS協議。

本文提出的HCTRP-PEGASIS改進協議雖然延長了網絡的壽命，但是其壽命時間有待延長。今后需要繼續優化該算法的主鏈建鏈方式和孤獨節點的通信方式(著重研究孤獨節點的通信方式)，使之具有更長的網絡生命周期。

[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。國家自然科學基金項目(61401004)；安徽師范大學創新基金項目(2015cxsj121)。丁緒星，教授，主研領域：物聯網技術，汽車電子與數字信號處理。王婷婷，碩士生。褚浩，碩士生。李磊，碩士生。