代祖浩，陳俊強，代 陽

（1.武漢郵電科學研究院湖北武漢430074；2.東華理工大學測繪工程學院，江西南昌330013）

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）是一種分布式傳感網(wǎng)絡(luò)，主要作用是通過部署在環(huán)境中的節(jié)點感知并傳遞監(jiān)測到的環(huán)境信息。由于監(jiān)測點空間位置、能量限制、體積等眾多因素的影響，WSN中各個節(jié)點之間采用無線通信方式傳遞信息，通過不同的協(xié)議?？梢越M建出不同類型的多跳自組織網(wǎng)絡(luò)，其網(wǎng)絡(luò)配置靈活，支持傳感節(jié)點位置移動，還可以通過網(wǎng)關(guān)或者IP化的無線傳感網(wǎng)絡(luò)協(xié)議棧接入互聯(lián)網(wǎng)[1]，滿足信息時代的遠程化、智能化的監(jiān)測控制需求。無線傳感網(wǎng)絡(luò)的核心任務(wù)是對環(huán)境信息的采集、處理和傳輸，其與通訊技術(shù)和計算機技術(shù)一起組成了信息時代的三大支柱。由于無線傳感網(wǎng)絡(luò)節(jié)點部署后無法再獲得新的能源供給，因此如何減少能源消耗提升網(wǎng)絡(luò)壽命開始作為WSN研究的主要方向[2-4]。

文獻[5]提出的LEACH（LowEnergy Adaptive Clustering Hierarchy，基于低能量自適應(yīng)簇結(jié)構(gòu)算法）是經(jīng)典的簇結(jié)構(gòu)算法，但在選舉簇頭時并沒有兼顧節(jié)點的余下的能源信息。文獻[6]提出EDACH（EnergyDriven Adaptive Clustering Hierarchy）采用代理節(jié)點策略。文獻[7]提出的EECH（Energy Efficient Clustering Hierarehy）算法，能量越高的節(jié)點被選舉為簇頭的幾率越高。文獻[8]提出的EECHS算法在LEACH算法的基礎(chǔ)上，兼顧了節(jié)點的余下能量、距離信息來選擇簇頭（ClusterHeader，CH）。文獻[9]提出的分簇PTTC（Prim based TreeTopology Clustering algorithm for Wireless Sensor）算法兼顧了節(jié)點的所剩能量、被選舉為簇頭的概率選舉簇頭。但這些算法在路徑權(quán)值計算方面沒有考慮傳感設(shè)備所剩能源以及路徑傳輸所損耗的能量[10]。

文中探索了一種以PTTC算法為基礎(chǔ)改進優(yōu)化措施。簇頭數(shù)量和簇頭選擇依照PTTC算法，但是在計算所傳感器節(jié)點的權(quán)值和路徑權(quán)值的時候綜合考慮節(jié)點的剩余能量、是否簇頭、路徑發(fā)送接收損耗。根據(jù)計算所得權(quán)值利用prim算法[11]建立最優(yōu)化簇樹結(jié)構(gòu)并定時更新保持簇樹結(jié)構(gòu)最優(yōu)化。仿真結(jié)果表明，相較于PTTC算法改進后的算法能夠更加高效的使網(wǎng)絡(luò)能量消耗均攤在每個節(jié)點上，使得網(wǎng)絡(luò)能運行的更久的時間[12]。

1 相關(guān)工作

多屬性決策是指當結(jié)果由多種影響因素決定的條件下，確定最優(yōu)解決策略或排列出各類解決方案[13]。具體思路是采集數(shù)據(jù)，排列方案，遴選最優(yōu)。知名學者Yager[14]發(fā)表的有序加權(quán)平均算子（Ordered Weighted Average operator，OWA）思想，把影響因素對結(jié)果影響程序大小排序，依照影響程度賦予不同的權(quán)值后將各種因素進行加權(quán)匯總，以獲得更客觀準確的結(jié)果評判。本文利用OWA算子集中處理影響路徑權(quán)值的各種因素，減少主觀臆測帶來的不良影響，采用熵值最大化作為最終評判標準。

2 系統(tǒng)模型

2.1 算法描述

根據(jù)PTTC算法計算出最優(yōu)的簇頭CH個數(shù)以及每個傳感節(jié)點成為簇頭CH的概率后，開始分簇網(wǎng)絡(luò)拓撲結(jié)構(gòu)生成階段。網(wǎng)絡(luò)上電啟動以后，基站向單跳路徑范圍內(nèi)的節(jié)點廣播探測消息確定其和鄰居節(jié)點之間的單跳路徑權(quán)值，收到正確的回復以后更新其路徑權(quán)值路由表。收到探測消息的節(jié)點繼續(xù)給周圍除了發(fā)來探測消息來源方以外的其他鄰居節(jié)點發(fā)送探測消息，同樣的收到正確回復以后更新其路徑權(quán)值路由表。遍歷完所有節(jié)點以后利用Prim算法構(gòu)建簇樹，這樣將形成一個初步的、傳輸路徑最優(yōu)化網(wǎng)絡(luò)結(jié)構(gòu)。

在該算法中，信息傳遞路徑的規(guī)劃都考慮了節(jié)點余下能源、途經(jīng)的節(jié)點數(shù)、路徑上的能源消耗等因素。使得網(wǎng)內(nèi)節(jié)點的能源消耗更加平均，同時保持了信息傳遞路徑一直處于最優(yōu)化狀態(tài)，從而提高了網(wǎng)絡(luò)的存活壽命。

2.2 最優(yōu)簇頭數(shù)

PTTC算法首先采用了多徑衰落的信道模型建立了節(jié)點之間無線通訊的能量消耗模型，根據(jù)簇頭需要融合的數(shù)據(jù)得出網(wǎng)絡(luò)運行一輪簇頭耗費的能源表示公式。隨后根據(jù)節(jié)點到簇頭的距離和所要傳輸?shù)男畔⒋笮⊥茖總€子節(jié)點的能源消耗的表達式，進而得出簇內(nèi)總體能量消耗和簇頭個數(shù)的關(guān)系表達式。最后將總體能量消耗的表達式對簇頭個數(shù)求導計算出最優(yōu)的簇頭個數(shù)mbest：

其中k=λH=λ(4h4)是節(jié)點個數(shù)，H是傳感監(jiān)測區(qū)域的面積，，Enode為節(jié)點在收發(fā)信息時的能量消耗，εfa為多徑衰落的放大器因子，εra為自由空間放大器因子。

以此為基礎(chǔ)推導出節(jié)點擔任簇頭的概率pclu：

2.3 節(jié)點和路徑權(quán)值

系統(tǒng)啟動后基站開始向周邊廣播發(fā)送網(wǎng)絡(luò)參數(shù)信息，其中包括編號ID、所剩能源node()i.Er、自身參數(shù)status。節(jié)點將接收到的來自于鄰居的廣播信息存儲在鄰居信息表中，統(tǒng)計出鄰居節(jié)點總數(shù)。結(jié)合鄰居表中記錄的參數(shù)，綜合考慮多個因素的影響程度利用OWA算子確定各類影響因素的比重。最終計算出該節(jié)點的權(quán)值。用公式表達如下：

公式（1）里：F1是節(jié)點單跳范圍內(nèi)其他節(jié)點總數(shù)；F2是所剩能源參數(shù)；F3是傳感器距離基站的參數(shù)；v1、v2、v3表示上述因素的影響程度比重值的大小。對上述3個關(guān)鍵的影響因素使用下述公式進行歸一化運算：

式中：spot(m)?neinum為網(wǎng)絡(luò)節(jié)點i的單跳路徑內(nèi)的節(jié)點數(shù)；Nmax?neighbor為網(wǎng)絡(luò)節(jié)點擁有最多鄰居的數(shù)量值；Nmin?neighbor為網(wǎng)絡(luò)節(jié)點擁有最少鄰居的數(shù)量值；spot(m)?Pw為網(wǎng)絡(luò)節(jié)點m所余下的能源參數(shù)；spot(m)?Pmax為網(wǎng)絡(luò)節(jié)點m啟動前最大可用能量參數(shù)；spot(m)?lentoCS為網(wǎng)絡(luò)節(jié)點m離基站的間距長度；Lmax?toCS為離基站最遠節(jié)點到基站的距離；Lmin?toCS為離基站最近節(jié)點到基站的距離。

通過基于最大熵[15]的OWA的決策方法確定各個屬性的權(quán)重集合{v1，v2，v3} 的權(quán)重系數(shù)，并且將OWA算子中樂觀參數(shù)α設(shè)置成α=1/2。從而消除了決策者的憑空臆斷對結(jié)果選擇造成的不合理評判，同時將各類影響因素執(zhí)行歸一化計算表示之后能更準確的反映各類影響因素對簇頭選擇影響程度的權(quán)值[16]。

PPTC算法在確定路徑權(quán)值時只將跳數(shù)作為路徑權(quán)值來衡量路徑的優(yōu)劣，并沒有考慮到信息在路徑上傳遞時總共的能源消耗，同時即使是同一條路徑隨著路徑上節(jié)點剩余能量的不同，該路徑的權(quán)值也將隨之變化。所以為了使所有節(jié)點的能源消耗盡可能的均衡，需要周期性地尋找最佳路徑，定義路徑權(quán)值評估函數(shù)如下：

其中:v·spot(m)為接收路徑探測消息的節(jié)點m的權(quán)重參數(shù)；v·spot(n)為發(fā)送路徑探測消息的節(jié)點n的權(quán)重參數(shù)；spot(m)·consum(n)為發(fā)送方節(jié)點n到接收方節(jié)點m的路徑消耗的能源。該算法考慮到了路徑權(quán)值的關(guān)鍵因素：所剩能源、信息傳遞跳數(shù)、周圍鄰居數(shù)量、信息從起點到終點的能源消耗。

2.4 MST的構(gòu)建

在確定了最優(yōu)化的簇頭數(shù)量并選定了擔任簇頭的節(jié)點以后，開始簇樹結(jié)構(gòu)的生成階段。使用Prim算法構(gòu)建一個最小生成樹（Minimum Spanning Tree，MST）網(wǎng)絡(luò)的過程如圖1所示。構(gòu)建最小生成樹網(wǎng)絡(luò)的目的是為了保證網(wǎng)絡(luò)內(nèi)任意節(jié)點之間能夠通信的前提下使得網(wǎng)絡(luò)整體開銷最小化。

①設(shè)定初始狀態(tài)所有節(jié)點聚集在H中。從H中任意一點s出發(fā)并將點s放入集合K中。

圖1 基于prim算法構(gòu)建MST的過程

②在H-K剩余的節(jié)點中尋找一個節(jié)點t使其到K集合中的全部點的權(quán)值最小。之后將t節(jié)點放入集合K中。

③重復步驟②直到所有節(jié)點都加入集合K中。至此即可生成一個最小生成樹MST。如果H中包含M個節(jié)點，相應(yīng)的將生成M-1條邊[17]。

所有簇頭的最小生成樹網(wǎng)絡(luò)生成以后整體的簇樹網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示。在網(wǎng)絡(luò)運行階段，位于最末梢的傳感節(jié)點將采集到的信息傳遞給其上一級節(jié)點也就是其父節(jié)點，上一級節(jié)點隨后將信息傳遞給自己的上一級節(jié)點也就是父父節(jié)點，數(shù)據(jù)通過單向流動最終匯聚到了簇樹網(wǎng)絡(luò)的根節(jié)點也就是簇頭節(jié)點處執(zhí)行數(shù)據(jù)融合處理。采用Prim算法生成整體網(wǎng)絡(luò)拓撲結(jié)構(gòu)時，每一個簇頭都會形成一個最小生成樹網(wǎng)絡(luò)并擔任該MST最終的數(shù)據(jù)匯聚點進行數(shù)據(jù)融合處理，以實現(xiàn)各簇頭網(wǎng)絡(luò)之間以及簇頭網(wǎng)絡(luò)和基站之間的信息交換。

圖2 完整簇樹網(wǎng)絡(luò)結(jié)構(gòu)

3 算法性能分析

3.1 初始條件

在MATLAB環(huán)境進行仿真。仿真參數(shù)與PPTC算法保持一致。將節(jié)點隨機拋灑在100 m*100 m的領(lǐng)域中，基站部署在領(lǐng)域的中央。仿真初設(shè)參數(shù)設(shè)置如表1所示。

表1 仿真初設(shè)參數(shù)

在該相同的初始條件下選擇LEACH、PTTC算法與改進PTTC算法進行重復50次的同步仿真并計算平均值，單次運行時間500 s。并記錄對比結(jié)果。

3.2 能耗分析

3個算法的運轉(zhuǎn)輪數(shù)與能耗記錄如表2所示。從表2知在能耗50%時，LEACH、PTTC、改進PTTC分別運行了478輪、1 080輪、1 368輪。從運行相同的輪數(shù)來對比能量消耗，可以看出在運行到800輪時，LEACH、PTTC、改進PTTC分別消耗了48.67%、22.43%、18.52%的能量，可以看出改進PTTC算法比LEACH算法和PTTC算法能耗降低了30.15%、3.91%。

表2 3種算法運轉(zhuǎn)輪數(shù)與能量消耗

3.3 丟包率

圖3可知3種算法的丟包率都隨時間在上升，但改進的PTTC算法的丟包率一直處于最低。仿真結(jié)束前其最高丟包率為0.12%，說明本改進能保證良好的通訊質(zhì)量。LEACH算法丟包率最高，也從側(cè)面反映了隨機選擇簇頭會讓部分簇頭負載不均衡加劇簇頭能耗，造成部分簇頭早早死亡，導致網(wǎng)絡(luò)結(jié)構(gòu)斷裂，因而產(chǎn)生大量的丟包現(xiàn)象。

圖3 3種算法丟包率

4 結(jié) 論

針對PTTC算法中信息傳遞路徑固化，節(jié)點能源消耗不均衡等問題，設(shè)計了完善優(yōu)化算法。利用OWA算子集中處理所剩能源、兩點間通信能耗、節(jié)點自身權(quán)值等影響路徑權(quán)值的各種因素，以熵值最大化作為權(quán)值評判。該算法能長期保持節(jié)點數(shù)據(jù)傳輸?shù)淖顑?yōu)路徑。仿真結(jié)果顯示改進算法能更均衡網(wǎng)絡(luò)的能源消耗，使網(wǎng)絡(luò)運行更長時間。

[1]李鳳國.基于6LoWPAN的無線傳感器網(wǎng)絡(luò)研究與實現(xiàn)[D].南京:南京郵電大學，2013.

[2]覃俊翔，許小豐，易可夫，等.采用權(quán)函數(shù)計時的無線傳感器網(wǎng)絡(luò)分簇算法，計算機工程與應(yīng)用，2017（3）：138-143.

[3]張華南，李石君，金紅.無線傳感器網(wǎng)絡(luò)分簇路由節(jié)能研究[J].計算機工程與科學，2015，37（10）:1869-1876.

[4]姜參，王大偉.無線傳感網(wǎng)中一種能量均衡的分簇路由算法[J].計算機技術(shù)與發(fā)展，2014（1）:113-117.

[5] Heinzelmanwr，Chandrakasana，Balakrishnanh．Energy- efficientcommunication protocol for wirelessmicro-sensor networks[C].In Proc.HICSS，2000：1-10．

[6]Kimkt，Younghy．Energy driven adaptive clustering hierarchy（EDACH）for wireless sensor networks[J].LNCS，2005，38（23）：1098-1107．

[7]Huy，Liw，Kangz．Study on energy efficient hierar chical routing protocols of wireless sensor network[C]．InProc．ICIE．2009：325-328．

[8]Raya，Ded.Energy efficient clustering hierarchy protocolfor wireless sensor network[C].in Proc．ICCIA．201l：1-4．

[9]王智超.PTTC:無線傳感網(wǎng)絡(luò)分簇算法[J].電子技術(shù)應(yīng)用，2016（9）:91-94.

[10]石為人，柏蕩，高鵬，等.無線傳感器網(wǎng)絡(luò)簇頭半徑自適應(yīng)調(diào)節(jié)路由算法[J].儀器儀表學報，2012，33（8）:1779-1785.

[11]潘大志，陳友軍.Prim算法的一種優(yōu)化實現(xiàn)[J].西華師范大學學報：自然科學版，2011，32（1）:63-66.

[12]柳義筠.一種節(jié)能的無線Mesh網(wǎng)絡(luò)分簇路由協(xié)議[J].計算機與現(xiàn)代化，2012（6）:109-112.

[13]張小芝，朱傳喜，朱麗.一種基于變權(quán)的動態(tài)多屬性決策方法[J].控制與決策，2014（3）:494-498.

[14]Yager.WeightedmaximumentropyOWAaggregation with applications to decision making under risk[J].IEEE Transactions on Systems， Man， and Cybernetics-Part A:Systems and Humans，2009，39（3）:183-189．

[15]Yager R R．“Centered OWA operators”Soft Comput[J].soft Computing，2007，11（7）:631-639.

[16]王曉曉，馮巖，等.基于Q學習的無線傳感網(wǎng)分簇拓撲控制算法[J].鄭州大學學報：工學版，2015，36（2）:85-88.

[17]程媛媛.基于Prim最小生成樹算法的時間成本研究[J].河北北方學院學報：自然科學版，2013（6）:24-28.