基于OWA多屬性決策無(wú)線傳感網(wǎng)分簇算法

代祖浩，陳俊強(qiáng)，代 陽(yáng)

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

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

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

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

1 相關(guān)工作

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

2 系統(tǒng)模型

2.1 算法描述

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 MST的構(gòu)建

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

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

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

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

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

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

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

3 算法性能分析

3.1 初始條件

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

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

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

3.2 能耗分析

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

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

3.3 丟包率

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

圖3 3種算法丟包率

4 結(jié) 論

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

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

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

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

[4]姜參，王大偉.無(wú)線傳感網(wǎng)中一種能量均衡的分簇路由算法[J].計(jì)算機(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ú)線傳感網(wǎng)絡(luò)分簇算法[J].電子技術(shù)應(yīng)用，2016（9）:91-94.

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

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

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

[13]張小芝，朱傳喜，朱麗.一種基于變權(quán)的動(dòng)態(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學(xué)習(xí)的無(wú)線傳感網(wǎng)分簇拓?fù)淇刂扑惴╗J].鄭州大學(xué)學(xué)報(bào)：工學(xué)版，2015，36（2）:85-88.

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