鄭惠月，馮秀芳

（太原理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，山西 太原030024）

0 引 言

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

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

1 有向感知模型

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

圖1 有向感知模型

目標(biāo)P1被有向傳感器節(jié)點(diǎn)覆蓋的條件是：

2 多成員集群形成算法

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

在對(duì)集群算法進(jìn)行描述前，首先給出一些相關(guān)定義，如下所示。

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

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

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

2.1 MCA算法總體思想

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

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

2.2 MCA算法實(shí)現(xiàn)

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

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

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

K 代表傳感器節(jié)點(diǎn)的標(biāo)號(hào)。

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

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

3 節(jié)點(diǎn)調(diào)度

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

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

表1 多成員集群算法

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

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

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

第一優(yōu)先級(jí)與第二優(yōu)先級(jí)合作共同確立節(jié)點(diǎn)的優(yōu)先級(jí)，通過優(yōu)先級(jí)來調(diào)度網(wǎng)絡(luò)中的節(jié)點(diǎn)。

4 仿真實(shí)驗(yàn)

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

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

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

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

圖4 不同算法對(duì)活躍節(jié)點(diǎn)數(shù)的影響

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

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

圖5 不同算法對(duì)存活節(jié)點(diǎn)數(shù)量的影響

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

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

5 結(jié)束語

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

［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）. ［王 汝傳，孫力娟.無線多媒體傳感器網(wǎng)絡(luò)技術(shù) ［M］.北京：人民郵電出版社，2011：9－12.］

［4］LU Juan.Primary research on wireless multimedia sensor network ［J］.Popular Science，2012，14 （4）：73－74 （in Chinese）.［盧娟.無線多媒體傳感器網(wǎng)絡(luò)研究初探 ［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）. ［孫巖，馬華東.無線多媒體傳感器網(wǎng)絡(luò)QoS保障問題 ［J］.電子學(xué)報(bào)，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）.［顧曉燕，孫力娟，郭劍，等.無線傳感器網(wǎng)絡(luò)覆蓋質(zhì)量與節(jié)點(diǎn)休眠優(yōu)化策略 ［J］.計(jì)算機(jī)仿真，2011，28 （9）：127－131.］