基于細胞膜優化算法的WSN分簇協議研究

覃海生,何傳波,吳文俊,耿茂奎,蔣忠夏

(廣西大學計算機與電子信息學院,南寧530004)

基于細胞膜優化算法的WSN分簇協議研究

覃海生,何傳波,吳文俊,耿茂奎,蔣忠夏

(廣西大學計算機與電子信息學院,南寧530004)

針對無線傳感器網絡能量受約束的問題,為實現節點均衡能耗,平衡網絡簇頭分布,并最大限度地延長網絡壽命,提出一種基于細胞膜優化算法的無線傳感器網絡能量均衡分簇協議。細胞膜優化算法具有良好的全局尋優和快速收斂能力,通過濃度與能量因素對節點進行劃分,并結合距離因素完成全局均衡分簇,能夠解決傳感器網絡中簇頭分布不均勻、全局能耗不均衡等問題。實驗結果表明,該協議具有對無線傳感器網絡進行快速全局均衡分簇的能力,且與LEACH算法和LEAH-C算法相比,在均衡節點能耗和延長網絡生存周期等方面具有更好的性能。

無線傳感器網絡;均衡能耗;細胞膜優化算法;LEACH算法;LEACH-C算法

1 概述

無線傳感器網絡［1］(Wireless Sensor Network, WSN)通過傳感器節點感知、收集各種信息,并對其進行分析處理,從而實現遠程目標監控,是集信息采集、信息處理、信息傳輸于一體的綜合智能信息系統。由于節點多部署于無人看守區域,而且網絡節點的能量、計算能力與存儲能力都十分有限,特別是能量的限制,決定了網絡的壽命。利用分簇的層次路由［2］已經被證明在無線傳感網絡的擴展性、節點平衡能耗與網絡整體壽命的延長等方面有很好的優勢。

LEACH［3］(Low-energy Adaptive Clustering Hierarchy)算法是最早提出的應用于無線傳感網絡的層次路由算法。LEACH-C［4］(LEACH-Centralized)是一種集中式的簇頭選擇算法,將節點當前能量作為簇頭選取的條件,在高于全網平均能量的節點中尋找最佳的分簇方案、最小化的通信能量消耗。近年來,隨著對群智能優化算法的深入研究,結合群智能算法具有較好的自適應性、魯棒性強和可擴展性等特點,對基于群智能優化算法的無線傳感器網絡分簇路由算法的研究也取得了較大的成果。文獻［5］提出了基于動態人工魚群優化的WSN分簇算法。文獻［6-7］分別提出了在節點群智能算法上改進的無線傳感器網絡分簇算法。文獻［8-9］提出基于蟻群算法的對WSN分簇路由進行改進的算法。文獻［10］在人體血管網絡特性引入到無線傳感器網絡拓撲結構和分簇模式研究的基礎上進行了無線傳感器網絡非均勻等級分簇拓撲結構的研究。細胞膜優化［11］(Cell Membrane Optimization,CMO)算法通過研究細胞膜的特性及其物質轉運方式,從中進行提取優化模型,并結合全局優化算法的基本思想,提出了一種新型的全局優化算法,該算法具有很好的全局尋優能力、快速的收斂能力和獲取高精度解的能力。本文根據細胞膜優化算法的思想,提出了一種基于細胞膜優化算法的無線傳感網絡分簇協議。

2 基于細胞膜優化算法的分簇協議思想

2.1 細胞膜優化算法思想

細胞膜優化算法是通過研究細胞膜的特性及其物質轉運方式,從中進行提取優化模型,并結合全局優化算法的基本思想而提出的一種新型全局優化算法。細胞膜(Cell Membrane,CM)是細胞表面的一層薄膜。它是保證細胞內環境相對穩定的屏障,使細胞的各種活動能夠有序地運行。物質轉運方式主要有自由擴散、協助擴散、主動運輸、入胞和出胞等,前3種方式是重點研究的。脂溶性物質由膜的高濃度側向低濃度側的擴散過程稱為自由擴散。非脂溶性物質在膜蛋白(即載體)的幫助下,順濃度差跨膜擴散的程稱為協助擴散。離子或小分子物質在膜上“泵”的作用下,被逆濃度差的跨膜轉運過程,稱為主動運輸。自由擴散不需要載體也不需要能量,協助擴散只需要載體不需要能量,主動運輸既需要載體也需要能量［12］。

根據細胞膜轉運物質的過程,把物質分為3種:高濃度脂溶性物質,高濃度非脂溶性物質和低濃度物質。在最優化問題時,根據物質的濃度因子大小劃分為高濃度物質群和低濃度物質群,接著再把高濃度物質群進一步劃分為高濃度脂溶性物質和高濃度非脂溶性物質2個子物質群。

2.2 優化協議分簇流程

基于細胞膜優化算法的一次分簇協議思想包括以下7個步驟:參數的設定和初始化,節點劃分,脂溶性節點的運動,高濃度非脂溶性節點運動,低濃度節點運動,當前最優節點循環運動和節點的更新。協議流程見圖1。

圖1 優化協議流程

由協議可知,在每次循環結束后才對各節點群進行更新,算法結束的條件是滿足最優條件或者達到最大循環次數。

3 基于CMO的分簇協議

3.1 參數設定與節點初始化

把無線傳感網絡中的每個節點都抽象成算法中的節點,有n個節點則節點總數量為n;每次選擇簇頭的最大迭代次數為Gmax;計算節點濃度采用的半徑系數為r;當前最優節點停止搜索的臨界值pa;搜索半徑的收縮率為pb。

在無線傳感網絡中隨機部署n個節點,根據半徑系數r計算每個節點半徑內生存節點的濃度con。如節點i的濃度con定義為:其半徑內包含的所有有效節點到i節點的距離總和除以總節點數n乘以半徑的比值,即:

e為每個節點的能量與網絡平均能量的比值。每個節點因子值(p)由節點的濃度con與節點能量比值e確定,即p=a·con+b·e,其中,a+b=1且a,b都大于0。引入載體因子來調節節點運動的軌跡。每個節點的載體因子ε定義為:在2倍搜索半徑(2r)內所有有效節點到本節點距離的倒數和與總節點數n的比值。如式(2)所示:

ε為平均距離參數,ε大則半徑內的節點到本節點距離和較小,反之則較大。

3.2 節點的劃分

在n個節點中,按照因子值(p)的大小進行排序,根據表1的比例來劃分節點。

表1 節點劃分方式

按照表1的方式劃分出3種節點群,其中,X代表分配比例。最優解要通過多次迭代才能出現,所以不同的分配比例不會對每輪簇頭數量與最優解產生太大的影響。不過偏低或過高的X都會導致3種節點群比例差距大、3種節點群間抖動頻繁,延長最優解的迭代次數和3種節點群數穩定不變的迭代次數,增加計算量。綜合考慮在實驗中采用X為15%～20%的比例。

3.3 脂溶性節點的運動

每個高濃度脂溶性節點,如i節點,若半徑范圍內有低濃度節點群L或高濃度非脂溶性節點群HF的節點,保持脂溶性節點不變,并選擇距離自己最近的一個節點作為自己的臨時最優簇頭。若在節點搜索半徑內沒有非脂溶性節點或低濃度節點時,節點根據自身的能量選擇概率性擴散成為非脂溶性節點或保持不變。

3.4 高濃度非脂溶性節點的運動

高濃度非脂溶性節點在搜索半徑內與所有低濃度節點比較載體因子(ε),若存在ε大于某個低濃度節點則運動成低濃度節點,否則向半徑內的L群節點中選擇一個最優節點,然后向其擴散,成為脂溶性節點。

若搜索半徑內沒有低濃度節點,則與半徑距離內所有非脂溶性節點的ε比較,若自己最大則執行運輸成為低濃度節點。否則保持非脂溶性節點不變。

高濃度非脂溶性節點運動存在2種類型的運動形式,一種是向低濃度節點方向的協助擴散運動,另一種是向當前全局最優節點方向的運動。

3.5 低濃度節點的運動

對于低濃度節點,先判斷其能量是否滿足條件,若其不滿足大于平均能量的條件,直接變成脂溶性節點,并在半徑內尋找最優L群和HF群節點作為自己的臨時最優簇頭。

對于滿足能量條件的節點,算法同樣引入載體因子,進一步對低濃度節點的運動形式進行限制。接著判斷其是否滿足ε條件,如是否滿足在半徑距離內所有低濃度節點中ε最優,若滿足則依舊保留為低濃度節點,否則運動為高濃度非脂溶性節點。

低濃度節點運動存在3種類型的運動形式:第1種是節點在搜索域的隨機運動成為脂溶性節點;第2種是向高濃度節點方向運動的主動運輸成為高濃度非脂溶性節點;第3種是向當前全局最優節點方向的運動并保持低濃度節點的性質。

3.6 當前最優節點的循環運動

在優質節點附近往往會存在更優的節點,這樣不僅充分發掘當前最優節點鄰域內的節點空間,有利于種群的進化,更是對提高節點的精度有著重要的意義。

以低濃度節點作為當前最優節點并以其為中心,以半徑R進行搜索,R為:

其中,r為半徑系數,以pb=0.8的收縮速率進行。在半徑小于等于pa時退出搜索。在搜索過程中若存在全局最優解半徑和全局最優分簇,則接收這個解空間。在全局解空間中保存這個解和解半徑。

主要思想是:在半徑為2r開始比較簇頭間的成簇能耗,隨機試探性地在收縮半徑內把多個簇進行合并,如果合并后的總能量消耗小于合并前的總能量消耗的90%以上,則把多個簇合并成一個簇,減少全局的能量消耗。合并會導致簇成員增加,所以選擇出主從簇頭,合并后的最優主簇頭負責收集簇內成員的信息并融合,在多個簇中選擇一個從簇頭擔任和基站的聯系,這樣會大大減少全局能量消耗。如果此時的全局解優于前面的全局最優解,則接受這個解并保存到全局最優解與最優半徑中。繼續循環直至到達退出條件。在全部循環結束以后會產生本次循環的最優分簇和最優半徑。在最大循環次數的時候輸出全局最優分簇和最優半徑。

3.7 節點更新

在更新節點步驟中,把新的當前最優解和解半徑與原來的比較,若當前最優則替換原來最優解與解半徑,計數器重置為0;否則保留原最優解與解半徑,計數器加1。由新的3種節點群替換原來各自舊的節點群。要注意的是,所有節點只有在節點更新步驟才能進行更新節點,這是為了保證前面節點運動的并行性,也就是說,當代節點的產生只與上一代的節點有關,不與當代其他任何節點的變化有關。例如,在高濃度脂溶性節點運動的步驟中,高濃度脂溶性節點的運動需要低濃度節點和非脂溶性節點的參與,也可能產生非脂溶性節點。而在低濃度節點的運動中,也會產生脂溶性節點和非脂溶性節點,它們之間存在著交叉依賴關系。若采用時時更新,那么節點運動步驟出現的先后順序將影響進化的結果,同時也不利于算法的并行實現。

3.8 協議結束條件

在每次循環結束后都判斷計數器的值是否大于3(實驗統計3次以后還會產生可替代最優解的概率不到5%),大于3則認為滿足最優解條件或達到最大迭代次數Gmax(根據每個實驗環境測試決定),如果沒有滿足最優條件或未達到最大循環次數則轉到3.3節的步驟繼續執行。否則結束本輪簇頭選擇,輸出本輪選擇出的最優解和解半徑,作為本輪分簇的最優分簇,并按這個解進行分簇。

4 實驗結果與分析

4.1 實驗環境與參數設定

為了測試基于CMO算法的分簇協議的性能,本文算法的仿真測試在處理器為英特爾G530、內存2 GB的PC上,基于Matlab R2009a的環境模擬實現。仿真參數設置如下:在［200,200］m區域內隨機部署200個節點,Sink的初始位置在(0,0)m。半徑系數r=40 m,節點的初始能量都為1 J。本文實驗中所有輪數都是一次分簇包括5次數據傳送。

4.2 結果分析

圖2是本文算法的一次簇頭分布,其中,星號表示簇頭;圈表示普通節點。由圖2可以看出,該算法在簇頭節點的分布上相對比較均勻,這樣有利于全局能耗的均衡。

圖2 仿真模擬節點分布

為了解不同半徑對本文協議的影響情況,實驗對不同半徑下的網絡存活節點數進行了比較。

根據圖3的實驗結果表明,不同半徑對網絡的壽命還是有比較大的影響,因而在實際應用中針對實際的網絡情況,通過比較選擇出一個比較適合的半徑也相當重要。在本文實驗中半徑在30 m左右取得比較好的使用壽命。

圖3 本文協議在不同半徑下的存活節點數比較

圖4和圖5分別給出了不同半徑下每輪的簇頭數。根據比較可以看出,在半徑為30 m時,大部分時候簇頭數目穩定在12個～18個,簇頭數占總節點數0.6%～1%。但是半徑為40的時候簇頭數波動比較大,簇頭數目相對于30 m時少了2個 ～3個。2個簇頭數的比較:在半徑為30 m的簇頭數在300多輪的時候還保持了相對的穩定,而半徑為40 m的時候,簇頭數在200多輪的時候開始出現下滑趨勢,表明了網絡中開始出現死亡節點,也體現出半徑為30 m時能更好地延長整個網絡的壽命。

圖4 半徑為30 m的簇頭數目

圖5 半徑為40 m的簇頭數目

針對不同網絡節點分布情況下最優簇頭出現的迭代次數進行統計發現,最優的迭代次數多為6次～9次,而算法中3種節點穩定不變的迭代次數為10次～14次,表明了在產生最優解的時候3種節點還沒有穩定,而在隨后的迭代中沒有產生更優的解。在這一方面還要做進一步的研究,以使算法在節點群沒有穩定的時候產生更優解或者在節點群穩定的時候才應該產生最優解。

經過300次節點隨機分布進行實驗統計,圖6給出本文協議、LEACH算法和LEACH-C算法每輪節點存活數的比較,大部分LEACH算法第1個節點死亡的輪數是105輪左右,LEACH-C算法第1個節點死亡的輪數是176輪左右,而本文算法的第1個節點死亡集中在300輪左右,很好地延長了第1個節點的死亡時間。在網絡覆蓋上,LEACH算法和LEACH-C算法網絡的節點死亡都是在遠離基站的節點先死亡,導致在網絡節點數目下降的時候出現了覆蓋漏洞,而本文算法的節點死亡是隨機分布的,所以在較多的節點死亡情況下還能保持較好的覆蓋率。根據圖6也可以看出本文算法在網絡的整體壽命上也有較好的表現,延長了網絡壽命。

圖6 算法仿真比較

5 結束語

本文通過分析細胞膜算法的特點并與無線網絡分簇機制相結合,提出了一種基于細胞膜算法的無線傳感網絡分簇協議,對網絡分簇與全局能耗進行優化。協議通過節點的覆蓋率和剩余能量作為因子,利用細胞膜算法的全局尋優能力,在全局范圍中進行最優的分簇和簇內最低能耗的簇頭選擇方式,克服了網絡簇頭分布不均衡、各分簇能量消耗不平衡、總體網絡能耗達不到最優等問題。

通過實驗證明,基于細胞膜算法的分簇協議不僅均衡了全局網絡節點的能耗,還快速地對網絡進行全局分簇,降低網絡的總體能耗,延長了網絡的壽命。但是其在分簇過程中沒有考慮消息的路由傳送,今后將進一步優化分簇協議,研究節點跳數與最優路徑間的關系。

［1］ 鄔春學,肖 麗.基于蟻群算法的低能耗LEACH協議分析［J］.上海理工大學學報,2010,32(1):99-102.

［2］ 閆效鶯,程國建,孫 濤.一種能耗均衡的WSN分簇路由算法［J］.計算機工程,2012,38(14):79-81.

［3］ Heinzelman W,Chandrakasan A,Balakrishnan H.An Application-specific Protocol Architecture for Wireless MicrosensorNetworks［J］.IEEE Transactionson Wireless Communications,2002,1(4):660-670.

［4］ Siva D M G,Ma D C F.A Centralized Energy Efficient Routing Protocol for Wireless Sensor Networks［J］.IEEE Radio Communications,2005,43(3):8-13.

［5］ 劉向東,宋 欣,王翠榮.基于動態人工魚群優化的WSN分簇算法［J］.微電子學與計算機,2011,28(8): 43-46.

［6］ 范興剛,侯佳斌,介 靖,等.基于DPSO的智能WSN分簇路由算法［J］.傳感技術學報,2011,24(4): 593-600.

［7］ 李洪兵,余成波,閆俊輝,等.基于改進節點群聚類的無線傳感網絡能量均衡分簇策略［J］.計算機應用研究,2011,28(2):657-660.

［8］ 廖明華,張 華,謝健全.基于蟻群算法的WSN能量預測路由協議［J］.計算機工程,2012,38(3):88-90.

［9］ 蘇 兵,黃 娟.一種基于蟻群算法的WSN能效均衡路由［J］.微電子學與計算機,2012,29(11):50-52.

［10］ 李洪兵,熊慶宇,石為人.無線傳感器網絡非均勻等級分簇拓撲結構研究［J］.計算機科學,2013,40(2): 49-52.

［11］ 譚世恒,余衛宇.一種新型的全局優化算法——細胞膜優化算法［J］.計算機應用研究,2011,28(2): 455-457.

［12］ 譚世恒.一種新型的群智能優化算法——細胞膜優化算法及其應用［D］.廣州:華南理工大學,2011.

編輯 任吉慧

Research on Clustering Protocol of WSN Based on Cell Membrane Optimization Algorithm

QIN Haisheng,HE Chuanbo,WU Wenjun,GENG Maokui,JIANG Zhongxia
(College of Computer and Electronic Information,Guangxi University,Nanning 530004,China)

Aiming at energy constrained problems in Wireless Sensor Network(WSN),in order to achieve a balanced energy consumption of nodes,balance cluster heads distribution,and maximize the network lifetime,this paper proposes a WSN energy balanced clustering protocol which is based on the Cell Membrane Optimization(CMO)algorithms.The CMO algorithm has good ability of global optimization,and fast convergence capability.The new clustering protocol divides the nodes through concentration and energy factors.Combined with the distance factor for global clustering balance,it can be a good solution to the uneven distribution for cluster head,imbalanced global energy and other issues.Experiments show that the protocol has the capability of balanced global clustering quickly.Compared with LEACH algorithm and LEACH-C algorithm,it has better performance in terms of balancing power consumption and prolonging the network lifetime.

Wireless Sensor Network(WSN);balanced energy consumption;Cell Membrane Optimization(CMO) algorithm;LEACH algorithm;LEACH-C algorithm

1000-3428(2014)11-0092-05

A

TP393

10.3969/j.issn.1000-3428.2014.11.018

國家自然科學基金資助項目(61262072)。

覃海生(1956-),男,教授,主研方向:網絡與信息安全;何傳波、吳文俊、耿茂奎、蔣忠夏,碩士研究生。

2013-09-27

2014-01-02E-mail:hechuanbo40701@126.com

中文引用格式:覃海生,何傳波,吳文俊,等.基于細胞膜優化算法的WSN分簇協議研究［J］.計算機工程,2014, 40(11):92-96.

英文引用格式:Qin Haisheng,He Chuanbo,Wu Wenjun,et al.Research on Clustering Protocol of WSN Based on Cell Membrane Optimization Algorithm［J］.Computer Engineering,2014,40(11):92-96.