WMSNs多成員集群形成算法及節(jié)點調度

鄭惠月，馮秀芳

（太原理工大學 計算機科學與技術學院，山西 太原030024）

0 引 言

對于 無 線 多 媒 體 傳 感 器 網 絡［1－6］（wireless multimedia sensor networks，WMSNs）中 的 節(jié) 能 問 題，Alaei 等 在WMSNs中提出了一種分簇機制 （即單成員集群），其目的是創(chuàng)建多媒體節(jié)點間的協作能力以達到延長網絡生命周期的目的［7］。Kibrewerk使用機器學習算法自組織映射來減少傳輸信息量，達到延長網絡生命周期的目的［8］；文獻 ［9］提出了一種多重簇頭的無線傳感器網絡體系結構和一種基于節(jié)能和高效的路由協議，二者相互配合，在滿足實時數據的端對端延遲要求并確保最大化非實時數據的吞吐量的基礎上，降低了網絡的能耗提高了網絡的效率；文獻 ［10］提出了一種基于博弈論的分布式多信道分配機制，改善了在不同信道條件下的網絡性能參數，從而降低能耗；文獻［11］提出了一種對無線傳感器網絡覆蓋質量與節(jié)點休眠之間權衡關系的優(yōu)化策略，并采用粒子群算法尋求最優(yōu)組合，使網絡綜合性能得到了很大的提升。

由于無線多媒體傳感器網絡中，尤其是視頻傳感器，其傳感器節(jié)點的感知區(qū)域受 “視角”的限制，并非一個完整的圓形區(qū)域，因此本文采用有向感知模型，即方向可調感知模型。在此基礎上針對單成員集群算法 （single－membership clustering algorithm，SCA）不存在集群間相互協作，從而造成數據冗余和能量浪費的缺點，提出了一種多成 員 集 群 算 法 （multi－membership clustering algorithm，MCA），通過集群間的協作和節(jié)點調度功能來延長節(jié)點生命周期，減少采集信息以及處理、傳輸數據的冗余，降低能耗，延長整個網絡生命周期。

1 有向感知模型

在無線多媒體傳感器網絡中，其傳感器節(jié)點具有方向性和視角，所以節(jié)點的感知范圍是一個以節(jié)點為中心、感知距離為半徑的扇形區(qū)域。本文采用如圖1所示的有向感知模型。該模型可用一個四元組 （P，R，珗v，α）表示。P（x，y）表示有向傳感器節(jié)點位置的坐標；R 表示節(jié)點感知半徑；珗v 表示節(jié)點的主感知方向；2α為視角范圍。當α＝π時，是有向感知模型的一個特例，為全向感知模型。

圖1 有向感知模型

目標P1被有向傳感器節(jié)點覆蓋的條件是：

2 多成員集群形成算法

在SCA 算法中，每一個節(jié)點只能屬于一個集群，從而不存在集群間的合作，因而可能出現數據冗余的現象。為此，采用MCA 算法，即一個節(jié)點可以屬于多個集群，集群之間有公共節(jié)點，這樣集群間可進行相互協作，通過統(tǒng)一調度，可以降低數據冗余，節(jié)約能量，提高網絡性能。

在對集群算法進行描述前，首先給出一些相關定義，如下所示。

定義1 簇頭：在集群中作為判斷一個節(jié)點是否屬于本集群的參照節(jié)點，其它節(jié)點通過與其比較感知區(qū)域重疊度來確定是否屬于這個集群。

定義2 集群規(guī)模因子 （γ）：感知區(qū)域重疊度的閾值，即一個節(jié)點作為集群中成員與簇頭的最小重疊度，用來判斷一個節(jié)點是否屬于該集群。集群規(guī)模因子在集群算法開始執(zhí)行時被設置為一個定值，具體大小根據不同的應用需求來確定。

定義3 節(jié)點重疊度 （η）：是指與這個節(jié)點的感知重疊面積達到集群規(guī)模因子 （γ）的節(jié)點的數量。

2.1 MCA算法總體思想

在無線多媒體傳感器網絡監(jiān)測區(qū)域內隨機布置n個節(jié)點，其中每個節(jié)點都能夠確定自己的位置和方向，并在網絡部署完成后向匯聚節(jié)點發(fā)送自己的方位及狀態(tài)信息。首先根據具體的應用需求設置集群規(guī)模因子γ，然后從節(jié)點列表中找出一個還沒有集群的節(jié)點作為簇頭建立一個新的集群，網絡中所有的節(jié)點都在新集群被建立的時候與新集群簇頭節(jié)點進行計算測試能否成為其成員。當一個節(jié)點與簇頭節(jié)點感知區(qū)域的重疊面積百分比大于集群規(guī)模因子γ時，其即成為該集群的成員。如果一個節(jié)點經計算屬于多個集群，則將該節(jié)點加入其所屬的所有集群。

由于一個節(jié)點可能屬于多個集群，所以集群可能出現相交的情況。因此，在節(jié)點調度的時候，需要根據節(jié)點是否為公共節(jié)點、節(jié)點的剩余電量和節(jié)點前一階段的工作狀態(tài)來確定節(jié)點是否被選作簇頭，防止某個節(jié)點因被頻繁選作簇頭而使能量快速耗光而提前結束工作。然后簇頭調度集群內各個節(jié)點輪流工作，減少采集、傳輸和處理信息的冗余，節(jié)約能量，從而延長網絡的生存周期。

2.2 MCA算法實現

在WMSNs監(jiān)測區(qū)域內隨機部署n個傳感器節(jié)點，用集合S＝ ｛S1，S2，S3，…，Sn｝來表示，其中每個節(jié)點都能夠確定自己的位置和方向。

狀態(tài)向量SV 表示每個節(jié)點的狀態(tài)，其中0 代表未集群；1代表已集群；2代表簇頭；3代表共同節(jié)點。

SV 初值為＜0，…，0＞。

K 代表傳感器節(jié)點的標號。

算法終止條件：狀態(tài)向量SV 中不存在0狀態(tài)。

多成員集群算法 （MCA）具體描述見表1。

3 節(jié)點調度

為了減少網絡中采集、傳輸和處理信息的冗余，節(jié)約能量，延長網絡的生存周期。本文采用了一種專門針對多成員集群算法設計的調度算法，由于多成員集群允許集群重疊，所以集群內和集群間都可進行協作，將此調度方法稱為多成員集群調度 （multi－membership clustering scheduling，MCS）。MCS的主要思想如下：為了防止網絡中某個節(jié)點因被頻繁激活而使能量快速耗光而提前結束工作，需要根據一個節(jié)點是否為公共節(jié)點、節(jié)點的剩余電量和節(jié)點前一階段的工作狀態(tài)來綜合選取節(jié)點來輪流工作，所以需要為所有節(jié)點設立一個優(yōu)先級，根據優(yōu)先級的高低來選擇節(jié)點。在這里設立了兩類優(yōu)先級，即第一優(yōu)先級PL1 和第二優(yōu)先級PL2，并定義對于每個節(jié)點Si而言，其第一優(yōu)先級與第二優(yōu)先級之和決定了這個節(jié)點在被選作監(jiān)視節(jié)點過程中的總優(yōu)先級Pi。即

第一優(yōu)先級PL1 的目的在于選擇剩余能量盡量多，同時所屬集群盡量多的節(jié)點，這樣的節(jié)點由于剩余電量多，就可以更多次的完成監(jiān)測任務，同時由于隸屬度高，在其工作期間就可以有更多的節(jié)點處于休眠狀態(tài)。第一優(yōu)先級在每輪監(jiān)測開始前確定，是一個靜態(tài)的值，其定義為

表1 多成員集群算法

式中：ERi——節(jié)點Si當前剩余能量，EQi——在一個監(jiān)測周期內若節(jié)點Si活動所消耗的能量，ERi／EQi——節(jié)點Si在當前剩余能量的情況下能為整個網絡工作的次數，Wi——節(jié)點Si的隸屬度。

第二優(yōu)先級PL2 的目的是為了避免選擇在連續(xù)的監(jiān)測周期內監(jiān)測同一區(qū)域的節(jié)點，同時希望在當前監(jiān)測周期選擇與上個監(jiān)測周期監(jiān)測節(jié)點來自不同集群的節(jié)點。所有節(jié)點Si的第二優(yōu)先級PL2 初始均為0，即：＝0。

第二優(yōu)先級PL2 在每輪監(jiān)測周期內隨著監(jiān)測節(jié)點的選擇而變化，當一個節(jié)點被選擇為當前監(jiān)測周期的監(jiān)測節(jié)點后，其第二優(yōu)先級便降低避免下回合再選擇它，同時，與其在同一集群的其它節(jié)點的第二優(yōu)先級也降低，避免下回合選擇與上回合監(jiān)測同一區(qū)域的節(jié)點，即：＝－1。

第一優(yōu)先級與第二優(yōu)先級合作共同確立節(jié)點的優(yōu)先級，通過優(yōu)先級來調度網絡中的節(jié)點。

4 仿真實驗

（1）集群規(guī)模因子γ對集群規(guī)模和集群數目的影響：本實驗采用Matlab7.0實現，實驗中假設所有的傳感器節(jié)點都是同構的，即傳感器節(jié)點參數規(guī)模相同。在1000×1000m2的監(jiān)測區(qū)域內，部署感知半徑為100m、傳感夾角為45°的傳感器節(jié)點。圖2和圖3通過改變傳感器節(jié)點密度進行系統(tǒng)的性能分析。

圖2和圖3分別顯示了在不同的部署密度下，集群數目和集群規(guī)模與集群規(guī)模因子γ的關系。從圖3可以看出隨著集群規(guī)模因子γ的增加，集群數目也隨之增加，且節(jié)點部署密度越大，集群數目增長的越快。從圖4可以看出隨著集群規(guī)模因子γ的增大，集群規(guī)模逐步降低，且節(jié)點部署密度越大，集群規(guī)模降低的越明顯。

圖2 集群數目與集群規(guī)模因子的關系

圖3 集群規(guī)模與集群規(guī)模因子的關系

圖4 不同算法對活躍節(jié)點數的影響

（2）MCA 算法與傳統(tǒng)集群算法的比較：在以上分析的基礎上，采用不同的算法對比驗證MCA 算法在節(jié)約能耗上的效率。在進行網絡部署時，為了保證服務質量（QoS），通常采用冗余部署，但當節(jié)點密度較大時，由于節(jié)點感知區(qū)域的重疊較多，又會造成浪費，因此需要采用節(jié)點調度的方法來使節(jié)點輪換工作，從而節(jié)約網絡能耗，延長網絡生命周期。

本實驗以集群規(guī)模因子γ＝0.15為例來說明不采用集群算法、采用單成員集群算法和多成員集群算法時對網絡性能的影響。圖4顯示了采用不同算法時，在不同的節(jié)點部署密度情況下，網絡中的活躍節(jié)點數。圖5顯示采用不同算法時，網絡中存活節(jié)點的數量隨時間變化的趨勢。

圖5 不同算法對存活節(jié)點數量的影響

從圖4中可以看出，在不采用集群算法時，網絡中的節(jié)點在工作時全部處于活躍狀態(tài)，其優(yōu)點是獲取的信息豐富，相對準確，缺點是采集的信息量龐大，冗余數據非常多，在采集、處理以及傳輸過程中都對節(jié)點產生巨大能耗壓力；在采用成員集群算法時，與不采用集群算法相比，網絡中的活躍節(jié)點數有明顯的降低，這將很大程度的延長網絡的生命周期；在采用多成員集群算法時，網絡中的活躍節(jié)點數比單成員集群算法中更少，因為采用單成員集群算法時，節(jié)點只屬于一個集群，不存在節(jié)點間的協作，而多成員集群算法集群與集群間具有共同節(jié)點，可以通過MCS調度方法對節(jié)點進行協調調度，進一步降低需要工作的節(jié)點數。從圖4 還可以看出，在節(jié)點密度大的情況下，在多成員集群算法的效率更高，效果更好。

從圖5中可以看出，在不采用集群算法時，由于網絡中的所有節(jié)點在工作時會全部處于活躍狀態(tài)，所以網絡的生命周期等于其節(jié)點的生命周期。因為在網絡工作的時間內所有節(jié)點能量的消耗是一致的，所以當所有節(jié)點的能量同時耗盡時整個網絡也會隨之死亡；在采用集群算法后，圖中每一個下降的臺階都說明網絡中的一部分節(jié)點能量耗盡，但整個網絡還可以工作。在采用多成員集群算法后，整個網絡直到6.5T （T 為一個節(jié)點耗盡能量時所能工作的時間長度）時所有節(jié)點才全部死亡；而采用單成員集群算法也可以達到一個較好的網絡生存時長，可以達到4.5T，但是效果還是沒有采用多成員集群算法好，這是因為單成員集群算法只有簇內協作，沒有簇間協作。簇間協作可以進一步降低工作節(jié)點的冗余，提高網絡中節(jié)點整體的利用率，降低能量消耗。

5 結束語

本文針對單成員集群算法不存在集群間相互協作，從而造成信息冗余和能量浪費的缺點，提出了多成員集群算法，根據節(jié)點與簇頭的感知區(qū)域重疊率是否達到集群規(guī)模因子來判斷該節(jié)點是否屬于該集群，同時在集群間協作進行節(jié)點調度的過程中，根據節(jié)點是否為公共節(jié)點、節(jié)點的剩余電量和節(jié)點前一階段的工作狀態(tài)來決定是否喚醒該節(jié)點作為本輪的工作節(jié)點。仿真驗證了MCA 算法的高效性。實驗結果表明了在無線多媒體傳感器網絡的集群中采用MCA 算法，能在滿足網絡感知要求的前提下，有效提高網絡效率，節(jié)約能量，延長網絡的生命周期。

［1］Almalkawi IT，Zapata MG，Al－Karaki JN，et al.Wireless multimedia sensor networks：Current trends and future directions［J］.Sensors（Basel，Switzerland），2010，10 （7）：6662－6717.

［2］Kyildiz IF，Melodia T，Chowdhury KR.A survey on wireless multimedia sensor networks［J］.Computer Networks，2007，51 （4）：921－960.

［3］WANG Ruchuan，SUN Lijuan.Wireless multimedia sensor network technology ［M］.Beijing：The People’s Posts and Telecommunications Press，2011：9－12 （in Chinese）. ［王 汝傳，孫力娟.無線多媒體傳感器網絡技術 ［M］.北京：人民郵電出版社，2011：9－12.］

［4］LU Juan.Primary research on wireless multimedia sensor network ［J］.Popular Science，2012，14 （4）：73－74 （in Chinese）.［盧娟.無線多媒體傳感器網絡研究初探 ［J］.大眾科技，2012，14 （4）：73－74.］

［5］You L，Liu C，Tong S.The lifetime optimization of wireless multimedia sensor networks under uncertain energy consumption［C］／／5th International Conference on Computer Science and Education.IEEE，2010：928－932.

［6］SUN Yan，MA Huadong.The QoS guarantee problem for wireless multimedia sensor networks［J］.Journal of Electronic，2008，36 （7）：1412－1420 （in Chinese）. ［孫巖，馬華東.無線多媒體傳感器網絡QoS保障問題 ［J］.電子學報，2008，36（7）：1412－1420.］

［7］Alaei M，Barcelo－Ordinas JM.A method for clustering and cooperation in wireless multimedia sensor networks ［J］.Sensors，2010，10 （4）：3145－3169.

［8］Akalu K，Raimond K.Design and performance analysis of energy efficient technique for wireless multimedia sensor networks using machine learning algorithm ［C］／／World Congress on Information and Communication Technologies.IEEE，2011：1127－1132.

［9］Agrakhed J，Biradar GS，Mytri VD.Cluster based energy efficient QoS routing in multi－sink wireless multimedia sensor networks［C］／／7th IEEE Conference on Industrial Electronics and Applications.IEEE，2012：731－736.

［10］Khan ZA，Auguin M.A multichannel design for QoS aware energy efficient clustering and routing in WMSN ［J］.International Journal of Sensor Networks，2013，13 （3）：145－161.

［11］GU Xiaoyan，SUN Lijuan，GUO Jian，et al.Optimization strategy of coverage quality and node dormancy in wireless sensor networks ［J］.Computer Simulation，2011，28 （9）：127－131 （in Chinese）.［顧曉燕，孫力娟，郭劍，等.無線傳感器網絡覆蓋質量與節(jié)點休眠優(yōu)化策略 ［J］.計算機仿真，2011，28 （9）：127－131.］