吳　勇，張　靈

（廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣州510006）

基于多目標(biāo)優(yōu)化的WSN簇首選擇算法*

吳勇，張靈*

（廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣州510006）

分簇思想可以很好的用于優(yōu)化路由算法，現(xiàn)有的分簇算法簇首輪換選舉大多數(shù)只是從簇首和基站之間距離、節(jié)點(diǎn)密集度、剩余能量、節(jié)點(diǎn)位置等指標(biāo)來進(jìn)行改進(jìn)，沒有考慮候選簇頭距離各個(gè)簇首的平均距離。簇間轉(zhuǎn)發(fā)數(shù)據(jù)包會(huì)消耗大量能量，是影響網(wǎng)絡(luò)性能的一個(gè)重要因素。針對(duì)目前簇首輪換選舉算法存在的不足，提出了一種綜合考慮簇內(nèi)和簇間兩個(gè)優(yōu)化目標(biāo)的算法，此種算法本文簡(jiǎn)稱為DEDS。建立了候選節(jié)點(diǎn)剩余能量、候選簇頭節(jié)點(diǎn)距各個(gè)簇首節(jié)點(diǎn)平均距離等多目標(biāo)概率模型作為簇首輪換選擇依據(jù)。通過在NS2仿真平臺(tái)上驗(yàn)證了該算法在時(shí)延、分組遞交率、能耗、穩(wěn)定性等網(wǎng)絡(luò)性能優(yōu)于其它分簇算法。

無線傳感器網(wǎng)絡(luò)；簇首輪換；簇間平均距離；候選節(jié)點(diǎn)剩余能量；NS2；DEDS

EEACC:6150P；7230doi:10.3969/j.issn.1004-1699.2016.07.019

WSN是一種新型分布式無線傳感器網(wǎng)絡(luò)。是一種繼無線局域網(wǎng)和無線城域網(wǎng)技術(shù)之后的可以滿足對(duì)小型、短距離、低成本、低功耗的無線傳感器網(wǎng)絡(luò)技術(shù)需求而產(chǎn)生的。主要作用是采集數(shù)據(jù)以及進(jìn)行終端控制。

分簇思想可以很好的降低網(wǎng)絡(luò)能量消耗，是改進(jìn)整個(gè)網(wǎng)絡(luò)的性能之一［1-5］。分簇思想包括簇中簇首和基站的通信、簇首的選舉機(jī)制。已經(jīng)存在的分簇算法中簇首輪換選舉基本上是從簇首和基站之間距離、節(jié)點(diǎn)密集度、剩余能量、節(jié)點(diǎn)位置等因素進(jìn)行研究的，前人對(duì)這個(gè)問題的研究中沒有考慮候選簇頭距離各個(gè)簇首的平均距離。而簇間轉(zhuǎn)發(fā)數(shù)據(jù)包會(huì)消耗大量的能量，簇間負(fù)載不均衡會(huì)影響網(wǎng)絡(luò)性能。本文就是在前人的研究之上針對(duì)不足，將候選簇頭距離其它簇首節(jié)點(diǎn)的平均距離也考慮進(jìn)去從而在一定程度上優(yōu)化了網(wǎng)絡(luò)的性能。

1　相關(guān)工作

簇首比普通節(jié)點(diǎn)要繁忙很多，包括接收簇內(nèi)成員節(jié)點(diǎn)的數(shù)據(jù)包、數(shù)據(jù)融合以及簇間數(shù)據(jù)的轉(zhuǎn)發(fā)，因此簇首輪換選擇算法可以很好的優(yōu)化整個(gè)網(wǎng)絡(luò)的性能。文獻(xiàn)［5］中給出了一種在簇首選舉時(shí)僅考慮候選傳感器節(jié)點(diǎn)的剩余能量，并實(shí)現(xiàn)了部分的分簇負(fù)載均衡的算法，文中簡(jiǎn)稱為HEED算法，此算法沒能夠解決簇間不合理的距離。文獻(xiàn)［6］解決了節(jié)點(diǎn)數(shù)量不適中的問題，但沒有對(duì)節(jié)點(diǎn)的剩余能量進(jìn)行優(yōu)化。文獻(xiàn)［7-8］提出了同時(shí)考慮均衡簇內(nèi)節(jié)點(diǎn)數(shù)量和節(jié)點(diǎn)成員距離的算法，在文中分別稱為ACHS與EACHS。文獻(xiàn)［9］在一定程度上均衡了在節(jié)點(diǎn)之間能量的消耗。文獻(xiàn)［10］中提出了一種基于權(quán)值的非均勻分簇路由算法，不足之處是沒有很好的考慮簇首負(fù)載問題。文獻(xiàn)［11］中給出了一種動(dòng)態(tài)的依據(jù)距離基站的遠(yuǎn)近來調(diào)整簇半徑的算法在文中簡(jiǎn)稱為EDUC，在一定程度上避免了靠近基站的簇首過早死亡的問題，但沒能夠考慮簇首之間距離以及密集度等因素。文獻(xiàn)［12］中提出了一種負(fù)載均衡感知的無線傳感器網(wǎng)絡(luò)容錯(cuò)分簇算法。此算法沒有考慮到靠近基站的簇首由于過多轉(zhuǎn)發(fā)其它距離簇首較遠(yuǎn)的簇首數(shù)據(jù)包而過度消耗能量，造成靠近基站的簇首節(jié)點(diǎn)過早死亡。文獻(xiàn)［13］提出了一種基于粒子群優(yōu)化的基礎(chǔ)上，粒子群優(yōu)化在文中簡(jiǎn)稱為PSO的無線傳感器網(wǎng)絡(luò)非均勻分簇雙簇頭PSO-NUDC路由算法，該算法是基于PSO算法提出的分簇的雙簇頭的一種路由算法。該算法的不足之處，利用簇半徑減輕了靠近基站的簇首負(fù)擔(dān)，同時(shí)距離基站遠(yuǎn)的簇用兩個(gè)簇頭減輕了距離遠(yuǎn)的簇首負(fù)擔(dān)，二者的出發(fā)點(diǎn)剛好相反，算法中沒能夠提出一種平衡二者的機(jī)制。在此基礎(chǔ)上，文獻(xiàn)［14］提出了一種采用模糊學(xué)綜合考慮多個(gè)因素來在每個(gè)層中選出數(shù)量不同的簇頭，基于模糊理論的無線傳感器網(wǎng)絡(luò)多層分簇式路由算法在文中稱為MLFC，此算法的不足之處是沒能夠很好的權(quán)衡各個(gè)因素，沒能夠提出一種很好的簇首選舉機(jī)制。

以上是針對(duì)組簇的研究，簇首由于比普通節(jié)點(diǎn)繁忙很多，網(wǎng)絡(luò)運(yùn)行一段時(shí)間后能量會(huì)過早耗盡，于是對(duì)簇首選擇算法的研究是很有必要的。文獻(xiàn)［15］吳玉成，李偉琪，胡真等人提出根據(jù)節(jié)點(diǎn)剩余能量和位置輪換選舉簇首來降低簇首能耗的算法，文中稱為RECR算法。文獻(xiàn)［16］辛玲，陳滌，李耀偉等人提出在競(jìng)選簇頭時(shí)把衡量鏈路質(zhì)量的指標(biāo)LQI作為可慮因素。文獻(xiàn)［17］譚軍提出一種在綜合考慮節(jié)點(diǎn)剩余能量、網(wǎng)絡(luò)平均剩余能量、上一輪節(jié)點(diǎn)消耗的基礎(chǔ)上，引入加權(quán)因子選擇簇首機(jī)制的算法文中稱為M-LEACH。文獻(xiàn)［18］中沈夢(mèng)南，耿剩玲，劉震等人提出了一種網(wǎng)絡(luò)運(yùn)行期間結(jié)合能量等考慮，分階段采用不同的簇頭和通信機(jī)制的算法稱為CR-SSCA。文獻(xiàn)［19］郭普秦，韓焱結(jié)合了節(jié)點(diǎn)剩余能量、節(jié)點(diǎn)密度和簇頭選擇時(shí)間作為簇首輪換選擇依據(jù)的算法，文中稱為DCWSN算法。文獻(xiàn)［20］中蔣暢江，王平，石為人等人提出了優(yōu)化時(shí)間作為簇首選擇依據(jù)的算法，文中稱為DEBUG。文獻(xiàn)［21］中陳炳才，李寶君，楊明川等提出同時(shí)去優(yōu)化能量消耗因子和節(jié)點(diǎn)之間距離等因子去修改LEACH協(xié)議中路有算法閥值的CMRAOL協(xié)議。文獻(xiàn)［22］中孫龍，徐榮，馬菲等提出基于能量變化為依據(jù)確定簇頭個(gè)數(shù)，同時(shí)以鄰接點(diǎn)個(gè)數(shù)、節(jié)點(diǎn)剩余能量作為簇首選擇依據(jù)的算法，文中稱為URCC。

為了彌補(bǔ)這些不足，本文給出DEDS算法以簇內(nèi)候選節(jié)點(diǎn)剩余能量以及距離其它簇首節(jié)點(diǎn)之間的平均距離等多個(gè)簇內(nèi)簇間目標(biāo)概率模型當(dāng)作簇首輪換選擇的依據(jù)。算法依據(jù)文獻(xiàn)［12］將簇首傳感器節(jié)點(diǎn)剩余總能量、簇內(nèi)傳感器節(jié)點(diǎn)數(shù)量、簇內(nèi)傳感器節(jié)點(diǎn)到簇首的平均距離、簇首平均距離作為簇首權(quán)重依據(jù)進(jìn)行組簇。網(wǎng)絡(luò)運(yùn)行到一定時(shí)間，依據(jù)簇首和基站的距離動(dòng)態(tài)調(diào)整簇半徑進(jìn)行分簇，簇首節(jié)點(diǎn)和基站之間采用多跳進(jìn)行通信，在此之上給出動(dòng)態(tài)更換簇首算法優(yōu)化，同時(shí)優(yōu)化候選節(jié)點(diǎn)的剩余能量、和其它簇首平均距離等簇內(nèi)簇間目標(biāo)。通過如（7）所示的加權(quán)公式：Pf=λW1+（1-λ）W2，選擇權(quán)值最大的候選節(jié)點(diǎn)充當(dāng)簇首，有效延遲了第一個(gè)節(jié)點(diǎn)死亡出現(xiàn)的時(shí)間。

2　DEDS路由算法

本文提出基于簇內(nèi)和簇間等多目標(biāo)優(yōu)化的WSN簇首選擇算法，并在NS2仿真平臺(tái)上進(jìn)行了驗(yàn)證比較，證明該算法在分組遞交率、時(shí)延、能耗、丟包率、穩(wěn)定性等網(wǎng)絡(luò)性能優(yōu)于別的分簇算法。

2.1能量模型

通過文獻(xiàn)［11］獲知無線傳感器網(wǎng)絡(luò)中消耗的能量主要包括數(shù)據(jù)接收以及發(fā)送，節(jié)點(diǎn)發(fā)送b bit數(shù)據(jù)能量消耗如式（1）所示

節(jié)點(diǎn)接收b bit數(shù)據(jù)能量消耗如式（2）所示

本文中節(jié)點(diǎn)剩余能量記為：W1

式中：d代表發(fā)送節(jié)點(diǎn)與接收節(jié)點(diǎn)的距離，Eelec代表傳輸單位數(shù)據(jù)的能量消耗；εm代表傳輸和發(fā)送數(shù)據(jù)的電路單位消耗。n代表數(shù)據(jù)發(fā)送次數(shù)，m代表數(shù)據(jù)接收次數(shù)。

2.2DEDS中離散粒子群優(yōu)化引入

WSN分簇思想中，優(yōu)化簇首輪換選擇的算法相當(dāng)重要，本文把候選節(jié)點(diǎn)剩余能量、和其它簇首之間的平均距離等因子作為選擇簇首的依據(jù)。建立在PSO算法上。

PSO算法啟發(fā)于鳥群在社會(huì)中的行為，PSO利用了種群思想提出一種解決搜索問題的策略。其中粒子的位置代表一個(gè)被搜索空間中的潛在解，所有粒子存在能夠被優(yōu)化的函數(shù)并且可以確定其適應(yīng)值，粒子中還存在速度屬性可以決定飛翔的方向以及距離。算法中粒子位置和速度的更新方程依次可以表示為如式（4）和式（5）。其中OSti代表第i個(gè)粒子的最優(yōu)解，OSt代表種群的最優(yōu)值，c1和c2表示認(rèn)知因子，a1和a2是取值0到1的隨機(jī)數(shù)，Pi和Si則依次代表粒子的位置和速度。

2.3可行性分析

DEDS算法依據(jù)文獻(xiàn)［12］提出的二進(jìn)制編碼思想進(jìn)行簇首輪換選擇的依據(jù)，同時(shí)優(yōu)化簇內(nèi)和簇間等多個(gè)目標(biāo)當(dāng)作簇首輪換選擇的依據(jù)。提出自適應(yīng)函數(shù)進(jìn)行優(yōu)化進(jìn)行選擇，因此，此算法適合用于簇首輪換選擇問題的優(yōu)化中。

2.3.1編碼

對(duì)n個(gè)候選簇頭節(jié)點(diǎn)依次編號(hào)：1，2，…，n。一個(gè)粒子代表一個(gè)可行解，其中粒子每個(gè)時(shí)間點(diǎn)出現(xiàn)的位置用一個(gè)n維的0～1進(jìn)行排列，例如i在t時(shí)刻的位置表示為，其中代表第k個(gè)節(jié)點(diǎn)的位置。1代表被選擇為簇首，0代表非簇首節(jié)點(diǎn)。粒子中每個(gè)節(jié)點(diǎn)位被初始化為0～1之間的值，如果值小于預(yù)先設(shè)置的簇首比例，數(shù)值即會(huì)被初始化為1，否則默認(rèn)為0。t時(shí)刻粒子i個(gè)體極值以及粒子全局指導(dǎo)粒子依次表示為。以上編碼方式對(duì)于簇首選擇問題可以滿足編碼完備性的原則，編碼不同的粒子表示簇首選擇方案不同，對(duì)應(yīng)不同空間的可行解，編碼方式也滿足非冗余性的原則，但是卻存在不可行解，導(dǎo)致算法不能夠滿足健全性原則。可能存在全部的節(jié)點(diǎn)都沒能夠被選擇為簇首。為了避免這個(gè)問題，可以在初始化時(shí)保證不少于一個(gè)節(jié)點(diǎn)位置設(shè)定為1，就能夠確保算法健全性的原則。避免了在搜索過程中不可行解的出現(xiàn)。

2.3.2自適應(yīng)函數(shù)選擇

簇首比其它節(jié)點(diǎn)繁忙很多，數(shù)據(jù)的融合、簇首之間的通信和簇內(nèi)通信。致使簇首能量消耗更多。本文提出在簇首輪換選擇時(shí)同時(shí)考慮優(yōu)化候選節(jié)點(diǎn)的剩余能量和到其它簇首平均距離等多目標(biāo)作為簇首輪換選擇的依據(jù)。

算法同時(shí)優(yōu)化考慮簇內(nèi)和簇間作為簇首選擇的依據(jù)，候選簇頭成為簇首的權(quán)重如式（7）。其中λ取值根據(jù)實(shí)際應(yīng)用場(chǎng)景設(shè)定，節(jié)點(diǎn)密集度高的地方距離不是影響網(wǎng)絡(luò)性能的主要因素，故優(yōu)先考慮能量，λ值取大點(diǎn)。而在節(jié)點(diǎn)稀疏的地方距離因素起著決定性作用，因此λ值取值小一點(diǎn)。

本文PSO算法中的候選簇首選擇流程如圖1所示。

圖1　簇首選舉流程圖

2.4多目標(biāo)優(yōu)化簇首輪換機(jī)制形成

算法規(guī)定，CH代表簇首節(jié)點(diǎn)、GW代表網(wǎng)關(guān)節(jié)點(diǎn)、CM代表簇成員。依據(jù)文獻(xiàn)［10］式（6）計(jì)算得到最優(yōu)分簇個(gè)數(shù)為k。算法中定義zbrcf_info的結(jié)構(gòu)體，包括節(jié)點(diǎn)類型、簇內(nèi)節(jié)點(diǎn)的Pf值、簇首權(quán)重Fit值、簇內(nèi)節(jié)點(diǎn)個(gè)數(shù)，將其加入信標(biāo)回復(fù)幀中。

2.4.1組簇流程

①首先協(xié)調(diào)器c建立一個(gè)網(wǎng)絡(luò)，形成第一個(gè)邏輯簇，并成為簇首節(jié)點(diǎn)。設(shè)定c節(jié)點(diǎn)的類型是CH。

②網(wǎng)絡(luò)中路由節(jié)點(diǎn)接收到對(duì)應(yīng)的信標(biāo)回復(fù)幀后，以簇首節(jié)點(diǎn)的能量和負(fù)載均衡多個(gè)因子作出相應(yīng)的選擇。

若信標(biāo)回復(fù)幀沒有發(fā)現(xiàn)簇首節(jié)點(diǎn)，則把自己的節(jié)點(diǎn)類型設(shè)定CH，父節(jié)點(diǎn)類型設(shè)定成網(wǎng)關(guān)GW，用以保證簇和簇之間存在相應(yīng)的網(wǎng)關(guān)進(jìn)行簇和簇之間的通信。

若只有一個(gè)簇首：把節(jié)點(diǎn)加入該簇，把相應(yīng)的節(jié)點(diǎn)類型設(shè)定為CM。

若網(wǎng)絡(luò)中存在多個(gè)簇首節(jié)點(diǎn)，則依據(jù)參考文獻(xiàn)［12］式（10），將節(jié)點(diǎn)加入到Fit最大的簇首節(jié)點(diǎn)所在的簇中，如果簇中不存在相應(yīng)的網(wǎng)關(guān)節(jié)點(diǎn)就將自己設(shè)定為GW.

③收到信標(biāo)回復(fù)的是終端節(jié)點(diǎn)，就依照步驟②的處理方式。

2.4.2簇首輪換選擇

網(wǎng)絡(luò)運(yùn)行一段時(shí)間之后，部分簇首節(jié)點(diǎn)因?yàn)槿蝿?wù)繁重而導(dǎo)致能量即將消耗殆盡，為防止簇首節(jié)點(diǎn)過早死亡進(jìn)而影響網(wǎng)絡(luò)的穩(wěn)定性，DEDS算法采用了簇內(nèi)和簇間多目標(biāo)簇首選擇算法，其步驟如下：

①當(dāng)簇首節(jié)點(diǎn)的能量是初始值的20%（這個(gè)閥值可以自行設(shè)定）時(shí)，通過廣播的方式通知其它屬于這個(gè)簇中的成員簇首失效，將簇首節(jié)點(diǎn)類型設(shè)定為CM。再依照以下方法重新選擇簇首

②結(jié)合考慮簇內(nèi)和簇間多目標(biāo)優(yōu)化的簇首選擇算法，在失效簇首的簇中依據(jù)簇首選擇流程圖1選出最佳簇首，并且將節(jié)點(diǎn)類型設(shè)定為CH.

③簇內(nèi)中的其它節(jié)點(diǎn)在收到簇首節(jié)點(diǎn)失效信息后，重新發(fā)起鄰居簇請(qǐng)求的信息，在收到新的簇信息之后，再次執(zhí)行簇形成如步驟②、步驟③。

3　在NS2平臺(tái)下仿真驗(yàn)證

3.1無線傳感器網(wǎng)絡(luò)仿真場(chǎng)景的建立

本文提出DEDS路由算法，并在NS2仿真平臺(tái)上和文獻(xiàn)［19］中提出的DCWSN算法以及文獻(xiàn)［22］提出的URCC算法比較，驗(yàn)證了該算法對(duì)網(wǎng)絡(luò)性能優(yōu)于其它算法，仿真場(chǎng)景設(shè)定邊長(zhǎng)為400 m×400 m的正方形監(jiān)測(cè)區(qū)域中部署30個(gè)傳感器節(jié)點(diǎn).仿真參數(shù)：網(wǎng)絡(luò)范圍：400 m×400 m；節(jié)點(diǎn)個(gè)數(shù)：30；仿真時(shí)間：7 min；通信半徑：50 m；節(jié)點(diǎn)初始能量：40 J；下圖2給出了場(chǎng)景中30個(gè)傳感器節(jié)點(diǎn)的拓?fù)鋱D。在圖2中只標(biāo)注了其中3個(gè)簇。

圖2　30個(gè)節(jié)點(diǎn)的拓?fù)浣Y(jié)構(gòu)

3.2分組投遞率

分組投遞率表示的是信宿接收分組數(shù)目與信源發(fā)送的分組數(shù)目之比。描述的是應(yīng)用層觀察的丟失率，最大吞吐量，路由協(xié)議算法完整性和正確性的指標(biāo)。這個(gè)指標(biāo)可以反應(yīng)出網(wǎng)絡(luò)傳輸?shù)目煽啃?，其?jì)算方法如下面的式（8）所示，其中Ps：表示發(fā)送的分組數(shù)；Pt：表示丟失的那些分組數(shù)；Pt：表示分組的遞交率。以圖3是URCC、DEDS、DCWSN算法分組投遞率的比較，隨著網(wǎng)絡(luò)運(yùn)行，控制分組的數(shù)目增多，所以三個(gè)算法的分組投遞率都有所降低。但DEDS簇首輪換機(jī)制考慮了簇間負(fù)載，在簇間轉(zhuǎn)發(fā)數(shù)據(jù)包跳數(shù)較少，故分組投遞率明顯高于其它兩個(gè)算法。其中橫坐標(biāo)代表節(jié)點(diǎn)個(gè)數(shù)，縱坐標(biāo)代表分組投遞率。

圖3　分組投遞率

3.3平均剩余能量百分比

平均剩余能量百分比反映了網(wǎng)絡(luò)中當(dāng)前剩余能量與網(wǎng)絡(luò)的初始能量比值。計(jì)算公式如式（9）。圖4是URCC、DEDS、DCWSN平均剩余能量百分比的比較情況，由于DEDS簇首輪換選擇算法優(yōu)化了簇間負(fù)載，在簇間數(shù)據(jù)包轉(zhuǎn)發(fā)的跳數(shù)較其它兩種算法少，轉(zhuǎn)發(fā)的RREQ數(shù)據(jù)包明顯小于其它算法，故能耗低于其它兩個(gè)算法，其中DEDS算法中由于一開始網(wǎng)絡(luò)運(yùn)行，轉(zhuǎn)發(fā)的RREQ數(shù)據(jù)包多，網(wǎng)絡(luò)運(yùn)行在1min前能量降得比較快，之后網(wǎng)絡(luò)運(yùn)行趨于平緩，其中橫坐標(biāo)表示節(jié)點(diǎn)個(gè)數(shù)，縱坐標(biāo)表示平均剩余能量百分比。

圖4　平均剩余能量百分比

3.4平均路由開銷百分比

平均路由開銷百分比統(tǒng)計(jì)的是網(wǎng)絡(luò)層內(nèi)平均傳遞一個(gè)數(shù)據(jù)分組所需要傳遞的控制信息，即控制分組數(shù)，反應(yīng)的是路由協(xié)議的平均有效傳輸率。其計(jì)算公式如式（10）。也稱為控制開銷，其中Pc（i）：表示傳輸數(shù)據(jù)i所需要花費(fèi)的控制分組數(shù)；Ps（i）：表示傳遞數(shù)據(jù)i所接收到的數(shù)據(jù)分組數(shù)。圖5是URCC、DEDS、DCWSN算法在平均路由開銷百分比上的比較。DEDS算法轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)考慮簇間的距離，跳數(shù)較少，故轉(zhuǎn)發(fā)的RREQ分組少于其它兩個(gè)算法，路由開銷小于其它兩個(gè)算法。如下所示，其中橫坐標(biāo)代表節(jié)點(diǎn)數(shù)目，縱坐標(biāo)代表平均路由開銷百分比。

圖5　平均路由開銷

3.5死亡節(jié)點(diǎn)數(shù)

網(wǎng)絡(luò)中節(jié)點(diǎn)死亡個(gè)數(shù)反映了網(wǎng)絡(luò)的穩(wěn)定性，DEDS算法中簇首輪換選擇的優(yōu)化明顯優(yōu)于其它兩個(gè)算法，DEDS算法考慮了候選簇頭和其它簇首之間的平均距離，輪換時(shí)選出的簇首轉(zhuǎn)發(fā)數(shù)據(jù)包的跳數(shù)短，消耗的能量少，所以相對(duì)來說DEDS算法中第一個(gè)死亡節(jié)點(diǎn)比其它兩個(gè)算法更慢，在第3 min才出現(xiàn)。如圖6所示。

圖6　死亡節(jié)點(diǎn)數(shù)

3.6丟包率

DEDS路由算法將簇間距離考慮到簇首選舉中，因此減短了簇間轉(zhuǎn)發(fā)路徑，轉(zhuǎn)發(fā)的RREQ減少，從而降低網(wǎng)絡(luò)擁塞度，結(jié)果也顯示算法至始至終優(yōu)于URCC和DCWSN。如圖7所示。

圖7　丟包率

4　結(jié)束語

簇首在整個(gè)簇中起著至關(guān)重要的作用。簇首任務(wù)相對(duì)普通節(jié)點(diǎn)要繁重得多。對(duì)于簇首輪換選擇的研究也是目前的熱點(diǎn)。DEDS算法從多個(gè)目標(biāo)來優(yōu)化簇首選擇的算法。已經(jīng)存在的簇首輪換方案中沒有考慮簇間負(fù)載，簇間轉(zhuǎn)發(fā)數(shù)據(jù)包會(huì)消耗大量能量，針對(duì)簇首輪換選擇的不足，本文給出了基于多目標(biāo)優(yōu)化的WSN簇首選擇算法，同時(shí)結(jié)合節(jié)點(diǎn)剩余能量、候選簇頭節(jié)點(diǎn)和其它各個(gè)簇首節(jié)點(diǎn)之間的平均距離等多個(gè)目標(biāo)概率模型來作為簇首輪換選擇的依據(jù)。最后在NS2仿真平臺(tái)上證明了DEDS路由算法在能耗、穩(wěn)定性等性能方面明顯優(yōu)于URCC和DCWSN。

［1］ Heinzelman W R，Chandrakasan A P，Balakrishnan H.Energy Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proceedings of the 33 rd Hawaaian International Conference on System Sciences.Hawaaian：IEEE，2000：3005-3014.

［2］ 李方敏，劉新華，徐文君，等.無線傳感器網(wǎng)絡(luò)的鏈路穩(wěn)定成簇與功率控制算法［J］.計(jì)算機(jī)學(xué)報(bào)，2008，31（6）：968-978.

［3］ 劉鐵流，巫詠群.基于能量?jī)?yōu)化的無線傳感器網(wǎng)絡(luò)分簇路由算法研究［J］.傳感技術(shù)學(xué)報(bào)，2011，24（5）：767-770.

［4］ 劉林峰，劉業(yè).一種無線傳感器網(wǎng)絡(luò)拓?fù)涞膯l(fā)式分簇控制算法［J］.計(jì)算機(jī)研究與發(fā)展，2008，45（7）：1099-1105.

［5］ Lin C H，Tsai M J.A Comment on“HEED：A Hybrid，Energy-Efficient，Distributed Clustering Approach for ad Hocsensor Networks［J］.IEEE Transactions on Mobile Computing，2006，5（10）：1471-1472.

［6］ Zhang C，Su Y M，Liu Y.Dynamic Clustering Algorithm with Balanced Load in Wireless Sensor Networks［C］//Proceedings of the 2009 2nd IEEE Internatonal Conference on Computer Science and Information Technology.MONASH University：IEEE，2009：177-181.

［7］ Nam C，Jeong H，Shin D.The Adaptive Cluster Head Selection in Wireless Sensor Networks［C］//Proceedings of the IEEE International Workshop on Semantic Computing and Application.Piscataway：IEEE，2008：147-149.

［8］ Nam C，Ku Y，Yoon J，et al.Cluster Head Selection for Equal Cluster Size in Wireless Sensor Networks［C］//Proceedings of the IEEE New Trends in Information and Service Science.Sungkyyunkwan University：IEEE，2009：618-623.

［9］ 蔡海濱，珺小明，曹奇英.多級(jí)能量異構(gòu)無線傳感器網(wǎng)絡(luò)的能量預(yù)測(cè)和可靠聚簇路由協(xié)議［J］.計(jì)算機(jī)學(xué)報(bào)，2009，32（12）：2393-2402.

［10］喬學(xué)工，王哲，王華倩.基于權(quán)值的非均勻分簇路由算法［J］.傳感技術(shù)學(xué)報(bào)，2014，1（1）：108-112.

［11］劉方愛，張春花，吳楠.WSN中基于能量和距離的自適應(yīng)分層路由算法［J］.計(jì)算機(jī)應(yīng)用研究，2014，11（31）：3434-3437.

［12］蘇金樹，郭文忠，余朝龍，等.負(fù)載均衡感知的無線傳感器網(wǎng)絡(luò)容錯(cuò)分簇算法［J］.計(jì)算機(jī)學(xué)報(bào)，2014，37（2）：446-456.

［13］門順治，孫順遠(yuǎn)，徐保國(guó).基于PSO的無線傳感器網(wǎng)絡(luò)非均勻分簇雙簇頭路由算法［J］.傳感技術(shù)學(xué)報(bào)，2014，27（9）：1282-1286.

［14］陸亞芳，易可夫，馮緒，等.基于模糊理論的無線傳感器網(wǎng)絡(luò)分層分簇式路由算法［J］.傳感技術(shù)學(xué)報(bào)，2014，27（7）：934-938.

［15］吳玉成，李偉琪，胡真，等.一種基于分環(huán)的能量高效無線傳感器網(wǎng)絡(luò)分簇路由協(xié)議［J］.傳感器與微系統(tǒng)，2015，34（5）：8-11.

［16］辛玲，陳滌，李耀偉.WSN跟蹤中基于鏈路質(zhì)量的動(dòng)態(tài)簇簇內(nèi)通信機(jī)制［J］.傳感技術(shù)學(xué)報(bào)，2012，25（6）：848-853.

［17］譚軍.簇首選擇改進(jìn)的LEACH無線傳感器路由協(xié)議［J］.計(jì)算機(jī)應(yīng)用與軟件，2015，32（6）：172-173.

［18］沈夢(mèng)南，耿剩玲，劉震.基于LEACH的無線傳感器網(wǎng)絡(luò)混合優(yōu)化協(xié)議算法［J］.計(jì)算機(jī)應(yīng)用，2014，34（8）：2149-2154.

［19］郭普秦，韓焱.基于分布式層次化結(jié)構(gòu)的非均勻聚類負(fù)載均衡算法［J］.計(jì)算機(jī)應(yīng)用，2015，35（2）：333-336.

［20］蔣暢江，石為人，王平，等.能量均衡的無線傳感器網(wǎng)絡(luò)分均勻分簇路由協(xié)議［J］.軟件學(xué)報(bào)，2012，23（5）：1223-1232.

［21］陳炳才，楊明川，李寶君，等.一種基于LEACH協(xié)議改進(jìn)的簇間多跳路由協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2014，27（3）：374-377.

［22］孫龍，徐榮，馬菲.一種新的基于鏈簇式的WSN不均勻分簇路由協(xié)議［J］.計(jì)算機(jī)應(yīng)用與軟件，2015，32（1）：107-109.

吳勇（1991-），男，江西人，廣東工業(yè)大學(xué)在讀碩士。主要研究方向?yàn)橹悄軆?yōu)化算法研究與應(yīng)用，無線傳感網(wǎng)絡(luò)傳輸技術(shù)；

張靈（1968-），女，廣西人，博士，廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院教授。主要研究方向?yàn)橹悄軆?yōu)化算法研究與應(yīng)用，無線網(wǎng)絡(luò)傳輸技術(shù)。

WSN Cluster Head Selection Algorithm Based on Multi Target Optimization*

WU Yong，ZHANG Ling*
（School of Computer，Guangdong University of Technology，Guangzhou 510006，China）

Clustering can be very good for optimizing the routing algorithm，existing clustering algorithm cluster head rotation electoral majority only from the distance between the base station and the cluster head，node density，residual energy，node position and other indicators to improve，without considering the average distance between the candidate cluster head at various distances from the cluster head.Forwarding packets between clusters will consume a lot of energy is an important factor affecting network performance.In view of the shortcomings of the current cluster algorithm rotation exists，this paper presents an in considering the two clusters and between cluster algorithm optimization goals，such algorithm referred to as DEDS.The establishment of a candidate node residual energy，the candidate cluster head node average distance from each cluster head and other objective probability model selection as a cluster head rotation basis.On the NS2 simulation platform validated by the algorithm delay，packet delivery rate，energy consumption，network performance stability than other clustering algorithms.

wireless sensor network；cluster head rotation；average distance between clusters；candidate node residual energy；NS2；DEDS

TP393.01

A

1004-1699（2016）07-1062-06

項(xiàng)目來源：廣州市科技計(jì)劃科學(xué)研究項(xiàng)目（2014J4100228）

2016-01-09修改日期：2016-02-22