基于OWA多屬性決策無線傳感網分簇算法

代祖浩，陳俊強，代 陽

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

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

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

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

1 相關工作

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

2 系統模型

2.1 算法描述

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

在該算法中，信息傳遞路徑的規劃都考慮了節點余下能源、途經的節點數、路徑上的能源消耗等因素。使得網內節點的能源消耗更加平均，同時保持了信息傳遞路徑一直處于最優化狀態，從而提高了網絡的存活壽命。

2.2 最優簇頭數

PTTC算法首先采用了多徑衰落的信道模型建立了節點之間無線通訊的能量消耗模型，根據簇頭需要融合的數據得出網絡運行一輪簇頭耗費的能源表示公式。隨后根據節點到簇頭的距離和所要傳輸的信息大小推導每個子節點的能源消耗的表達式，進而得出簇內總體能量消耗和簇頭個數的關系表達式。最后將總體能量消耗的表達式對簇頭個數求導計算出最優的簇頭個數mbest：

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

以此為基礎推導出節點擔任簇頭的概率pclu：

2.3 節點和路徑權值

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

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

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

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

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

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

2.4 MST的構建

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

①設定初始狀態所有節點聚集在H中。從H中任意一點s出發并將點s放入集合K中。

圖1 基于prim算法構建MST的過程

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

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

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

圖2 完整簇樹網絡結構

3 算法性能分析

3.1 初始條件

在MATLAB環境進行仿真。仿真參數與PPTC算法保持一致。將節點隨機拋灑在100 m*100 m的領域中，基站部署在領域的中央。仿真初設參數設置如表1所示。

表1 仿真初設參數

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

3.2 能耗分析

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

表2 3種算法運轉輪數與能量消耗

3.3 丟包率

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

圖3 3種算法丟包率

4 結 論

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

[1]李鳳國.基于6LoWPAN的無線傳感器網絡研究與實現[D].南京:南京郵電大學，2013.

[2]覃俊翔，許小豐，易可夫，等.采用權函數計時的無線傳感器網絡分簇算法，計算機工程與應用，2017（3）：138-143.

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

[4]姜參，王大偉.無線傳感網中一種能量均衡的分簇路由算法[J].計算機技術與發展，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:無線傳感網絡分簇算法[J].電子技術應用，2016（9）:91-94.

[10]石為人，柏蕩，高鵬，等.無線傳感器網絡簇頭半徑自適應調節路由算法[J].儀器儀表學報，2012，33（8）:1779-1785.

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

[12]柳義筠.一種節能的無線Mesh網絡分簇路由協議[J].計算機與現代化，2012（6）:109-112.

[13]張小芝，朱傳喜，朱麗.一種基于變權的動態多屬性決策方法[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學習的無線傳感網分簇拓撲控制算法[J].鄭州大學學報：工學版，2015，36（2）:85-88.

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