基于分區(qū)的能耗均衡路由協(xié)議*

翟春杰，徐建閩，劉永桂*（.華南理工大學(xué)自動(dòng)化科學(xué)與工程學(xué)院，廣州5064；.華南理工大學(xué)土木與交通學(xué)院，廣州5064）

?

基于分區(qū)的能耗均衡路由協(xié)議*

翟春杰1，徐建閩2，劉永桂1*
（1.華南理工大學(xué)自動(dòng)化科學(xué)與工程學(xué)院，廣州510641；2.華南理工大學(xué)土木與交通學(xué)院，廣州510641）

摘要：為了均衡無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)能耗，增強(qiáng)網(wǎng)絡(luò)穩(wěn)定性，設(shè)計(jì)并實(shí)現(xiàn)了一種基于分區(qū)的能耗均衡路由協(xié)議。該協(xié)議設(shè)計(jì)了一種優(yōu)化的分區(qū)算法，將節(jié)點(diǎn)基于分區(qū)劃分而形成簇，解決了先前協(xié)議中簇的個(gè)數(shù)和分布的隨機(jī)性問題；在選舉簇首時(shí)，綜合考慮了節(jié)點(diǎn)剩余能量、簇內(nèi)節(jié)點(diǎn)能耗均衡、簇內(nèi)部總能耗三個(gè)方面，采用三級(jí)簇首選擇機(jī)制，選擇的簇首既能均衡節(jié)點(diǎn)能耗，又可以降低簇群總能量消耗；在數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)，普通節(jié)點(diǎn)選擇距離最近的簇首，在不超過通信距離閥值時(shí)，簇首可以隔層選擇下一跳簇首，有利于緩解無線傳感器網(wǎng)絡(luò)的“熱區(qū)效應(yīng)”。仿真結(jié)果表明：相比MEET和DREEM-ME路由協(xié)議，該協(xié)議能更好地均衡節(jié)點(diǎn)能耗、增強(qiáng)網(wǎng)絡(luò)穩(wěn)定性、改善網(wǎng)絡(luò)服務(wù)質(zhì)量。

關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)；能耗均衡；分區(qū)算法；簇首選擇機(jī)制

無線傳感器網(wǎng)絡(luò)與應(yīng)用高度相關(guān)，單一的路由協(xié)議不能滿足各種應(yīng)用需求。針對(duì)不同應(yīng)用的特點(diǎn)，人們研究了眾多的路由協(xié)議，這些路由協(xié)議主要分為兩類：平面型路由協(xié)議和層次型路由協(xié)議。

層次型路由協(xié)議將網(wǎng)絡(luò)劃分成許多簇，每個(gè)簇會(huì)選出一個(gè)簇首來執(zhí)行不同的任務(wù)，而簇內(nèi)其它節(jié)點(diǎn)則會(huì)成為簇成員，簇成員將感知到的數(shù)據(jù)傳送給簇首，由簇首執(zhí)行數(shù)據(jù)匯聚、融合來減少數(shù)據(jù)的重復(fù)性以及所需傳送的數(shù)據(jù)量，最后通過多跳的路由方式傳送給基站［1］。

LEACH［2］為最早提出的層次型路由協(xié)議，它可以有效降低節(jié)點(diǎn)能耗和延長(zhǎng)網(wǎng)絡(luò)壽命，但是由于節(jié)點(diǎn)等概率地隨機(jī)擔(dān)任簇首，能量較低的節(jié)點(diǎn)也有可能成為簇首，造成節(jié)點(diǎn)能耗不均，影響網(wǎng)絡(luò)壽命；數(shù)據(jù)轉(zhuǎn)發(fā)采用簇首到基站的單跳方式，這會(huì)導(dǎo)致距離基站遠(yuǎn)的節(jié)點(diǎn)會(huì)消耗過多能量。

首先，在簇首選擇方面，文獻(xiàn)［3-4］為了避免能量較低的節(jié)點(diǎn)擔(dān)任簇首，采用設(shè)定固定的最小能量閾值的方法來篩去剩余能量較少的節(jié)點(diǎn)，然而采用固定的最小能量閾值缺乏應(yīng)用靈活性，為了解決這個(gè)問題，文獻(xiàn)［5］采用了隨著網(wǎng)絡(luò)整體能量下降而動(dòng)態(tài)變化的節(jié)點(diǎn)剩余能量閾值。

然后，在數(shù)據(jù)轉(zhuǎn)發(fā)方面，為了解決LEACH中數(shù)據(jù)以單跳方式傳輸造成距離基站遠(yuǎn)的節(jié)點(diǎn)消耗過多能量的問題，文獻(xiàn)［6-8］在簇首和基站之間的通信采用多跳方式，這樣有利于節(jié)約簇首能量，延長(zhǎng)網(wǎng)絡(luò)周期。

為了均衡節(jié)點(diǎn)能耗、延長(zhǎng)網(wǎng)絡(luò)壽命，在選擇簇首時(shí)盡量避免剩余能量較低的節(jié)點(diǎn)［3-5］，在數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)多采用多跳方式［6-8］，但是這仍然無法改變簇分布不均和網(wǎng)絡(luò)“熱區(qū)效應(yīng)”的現(xiàn)象，針對(duì)這一問題，文獻(xiàn)［9-10］分別提出了MEET和DREEM-ME協(xié)議，為了使簇首分布均勻，在簇形成方面，它們將隨機(jī)分布的節(jié)點(diǎn)根據(jù)位置進(jìn)行分區(qū)，同一個(gè)分區(qū)中的節(jié)點(diǎn)構(gòu)成一個(gè)簇，選擇簇中剩余能量最大的節(jié)點(diǎn)作為簇首；在數(shù)據(jù)轉(zhuǎn)發(fā)方面，仍然采用多跳方式，普通節(jié)點(diǎn)可選擇距離最近的簇首，而不只是所屬簇的簇首，同時(shí)簇首選擇下一層級(jí)最近的簇首。所建立的簇，分布比較均勻，節(jié)點(diǎn)能耗更加均衡，但是分區(qū)不夠合理，簇首選擇標(biāo)準(zhǔn)單一，“熱區(qū)效應(yīng)”尚未有效地緩解。

本文在研究LEACH、MEET、DDR［11］等協(xié)議的基礎(chǔ)上，提出了基于分區(qū)的能耗均衡路由協(xié)議。該協(xié)議吸取了MEET、DREEM-ME等協(xié)議的分區(qū)思想，提出了一種更加合理的、可擴(kuò)展的分區(qū)算法，分區(qū)更加科學(xué)、均勻；在簇首選擇方面，綜合考慮節(jié)點(diǎn)剩余能量、簇內(nèi)節(jié)點(diǎn)能耗均衡、分區(qū)總能量消耗三個(gè)方面，選擇的簇首更加優(yōu)化；在數(shù)據(jù)轉(zhuǎn)發(fā)方面，普通節(jié)點(diǎn)不受所屬簇的限制，可選擇距離最近的簇首，同時(shí)所設(shè)計(jì)的下一跳簇首選擇算法可進(jìn)一步均衡節(jié)點(diǎn)能耗，有效地緩解了“熱區(qū)效應(yīng)”。

1　建立簇首競(jìng)爭(zhēng)簇

根據(jù)概率選擇簇首，由于簇首的分布隨機(jī)性很大，簇群的分布不均勻，導(dǎo)致節(jié)點(diǎn)能耗不均衡，影響網(wǎng)絡(luò)的壽命，本協(xié)議的關(guān)鍵之一在于將節(jié)點(diǎn)基于位置劃分，建立若干分布均勻的簇，這里的簇成員只參與競(jìng)爭(zhēng)簇首，稱為簇首競(jìng)爭(zhēng)簇，每一個(gè)競(jìng)爭(zhēng)簇只能選出一個(gè)簇首，這樣保證了簇首的分布達(dá)到較優(yōu)的狀態(tài)，有效地延長(zhǎng)了網(wǎng)絡(luò)的壽命。實(shí)現(xiàn)競(jìng)爭(zhēng)簇的劃分，要經(jīng)過兩個(gè)步驟，首先對(duì)區(qū)域分區(qū)，然后節(jié)點(diǎn)根據(jù)自身所處的位置確定所屬的分區(qū)，也就確定了所屬的競(jìng)爭(zhēng)簇。

1.1區(qū)域劃分

區(qū)域劃分的基本思想：根據(jù)鄰層簇首間以及簇首和競(jìng)爭(zhēng)簇內(nèi)普通節(jié)點(diǎn)之間的最大距離約束，將一個(gè)區(qū)域以基站為中心劃分成若干個(gè)層，再將每個(gè)層均勻地劃分成若干個(gè)分區(qū)。如圖1所示，將一個(gè)區(qū)域劃分為4層，每層又均勻地劃分出6或12個(gè)分區(qū)，下面說明以基站為中心的各圓半徑之間的關(guān)系。

設(shè)以基站由內(nèi)而外的圓的半徑分別為r1、r2、r3、r4，以基站由內(nèi)而外的層分別為A層、B層、C層和D層；由于節(jié)點(diǎn)通信時(shí)，能耗會(huì)隨著節(jié)點(diǎn)間的距離而變化，設(shè)d0為節(jié)點(diǎn)間通信距離門限值，距離小于d0的節(jié)點(diǎn)通信，能耗則符合慢衰落模型，反之，大于或等于d0的節(jié)點(diǎn)通信，其能耗則符合快衰落模型[12]。為使節(jié)點(diǎn)通信降低能耗，區(qū)域劃分有三大原則：其一，B層簇首距離基站的最大距離為d0；其二，相鄰兩層最鄰近競(jìng)爭(zhēng)簇的簇首間的最大距離為d0；其三，每層競(jìng)爭(zhēng)簇的普通節(jié)點(diǎn)與該競(jìng)爭(zhēng)簇簇首的最大距離小于d0。這樣在數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)，就保證了普通節(jié)點(diǎn)與簇首、簇首與簇首、簇首與基站之間通信的距離均小于d0，通信能耗符合慢衰落模型。

如圖2所示，基于以上3個(gè)劃分原則，在ΔPOQ中，由三角形面積公式可得

圖2　參數(shù)分析示意圖

同時(shí)由海倫公式可得

由式（1）和式（2）可得

從而得出了r1，r3，d0，θ之間的關(guān)系式

在ΔMON中，同理由三角形面積公式可得

由海倫公式可得

由式（4）和式（5）可得

從而得到了r4，d0，θ之間的關(guān)系。

同時(shí)由于第一條劃分原則可得

綜上，基于3個(gè)劃分原則基礎(chǔ)上所得到的區(qū)域劃分為四層的約束方程為：

1.2建立簇首競(jìng)爭(zhēng)簇

記S(i，j)為區(qū)域中第i層的第j個(gè)分區(qū)，i∈{A，B，C，D}，j∈{Ⅰ，Ⅱ，…，Ⅻ}，S(i，j).angle為該分區(qū)在以基站為圓心的角度區(qū)間，S(i，j).dista為該分區(qū)相對(duì)基站的軸向分布區(qū)間，其中

S(i，j).angle=(S(i，j).angle.orig，S(i，j).angle.end]

S(i，j).dista=(S(i，j).dista.orig，S(i，j).dista.end]

這里的S(i，j).angle.orig，S(i，j).angle.end，分別為該分區(qū)相對(duì)于基站的起始角度和終止角度，S(i，j).dista.orig，S(i，j).dista.end分別為該分區(qū)相對(duì)于基站軸向的起始距離和終止距離。

如圖3所示可以清楚地獲悉S(C，Ⅱ).angle.orig，S(C，Ⅱ).angle.end，S(C，Ⅱ).dista.orig，S(C，Ⅱ).dista.end的具體含義。

設(shè)有N個(gè)節(jié)點(diǎn)隨機(jī)分布在區(qū)域內(nèi)，通過TSTOA[13]定位算法，可以得到每個(gè)節(jié)點(diǎn)相對(duì)于基站的方位，并進(jìn)一步獲取節(jié)點(diǎn)相對(duì)于基站的角度和距離的信息，記s(k)為第k個(gè)節(jié)點(diǎn)，s(k).angle和s(k).dista分別為該節(jié)點(diǎn)相對(duì)于基站的距離和角度，s(k).layer 和s(k).sec為該節(jié)點(diǎn)所屬的層和在該層的分區(qū)，若節(jié)點(diǎn)的方位滿足

則s(k).layer=i，s(k).sec=j即確定了節(jié)點(diǎn)所屬的分區(qū)，該分區(qū)的所有節(jié)點(diǎn)就構(gòu)成了簇首競(jìng)爭(zhēng)簇，競(jìng)爭(zhēng)簇形成算法如圖4所示。

圖3　距離、角度概念的示意圖

圖4　傳感節(jié)點(diǎn)劃分算法流程圖

2　簇首選擇

節(jié)點(diǎn)隨機(jī)分布在區(qū)域后，根據(jù)它們的方位信息就可以確定其所屬的分區(qū)，這樣分區(qū)中所有的節(jié)點(diǎn)組成一個(gè)簇，如何選擇簇首以便增強(qiáng)網(wǎng)絡(luò)的穩(wěn)定性，提升網(wǎng)絡(luò)的服務(wù)質(zhì)量是本協(xié)議的第2個(gè)關(guān)鍵。

2.1能耗模型

節(jié)點(diǎn)的能耗集中在節(jié)點(diǎn)工作期間，節(jié)點(diǎn)休眠時(shí)的能耗很小，在建立能耗模型時(shí)，主要考慮節(jié)點(diǎn)工作能耗，而工作能耗包括接收數(shù)據(jù)時(shí)的接收能耗和發(fā)送數(shù)據(jù)時(shí)的發(fā)送能耗；考慮發(fā)射端與接收端受距離影響的信號(hào)衰落，包括自由空間衰落和多徑效應(yīng)，便得到如下發(fā)送和接收單位比特的節(jié)點(diǎn)能耗表達(dá)式［12］

其中Tenergy為節(jié)點(diǎn)發(fā)送單位比特?cái)?shù)據(jù)的能耗，Renergy為節(jié)點(diǎn)接收單位比特?cái)?shù)據(jù)的能耗，Eelec為發(fā)送電路和接收電路的能耗，d0為收發(fā)兩端距離的門限值，εfs，εamp為相應(yīng)衰落的恒定參數(shù)。

在數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)，普通節(jié)點(diǎn)根據(jù)距離最近的原則選擇加入某個(gè)簇首，這樣就建立了基于簇首的數(shù)據(jù)轉(zhuǎn)發(fā)簇，若數(shù)據(jù)轉(zhuǎn)發(fā)簇中至少存在一個(gè)普通節(jié)點(diǎn)，可以建立下面的數(shù)據(jù)轉(zhuǎn)發(fā)能耗模型，這里只是考慮數(shù)據(jù)轉(zhuǎn)發(fā)簇內(nèi)的能耗模型。

若簇首為區(qū)域第j個(gè)簇首，其所在的數(shù)據(jù)轉(zhuǎn)發(fā)簇就記為j個(gè)數(shù)據(jù)轉(zhuǎn)發(fā)簇，則簇內(nèi)普通節(jié)點(diǎn)s(i)向簇首發(fā)送li比特?cái)?shù)據(jù)的能耗為

簇首接收節(jié)點(diǎn)s(i)發(fā)來的li比特?cái)?shù)據(jù)的能耗為

則所有普通節(jié)點(diǎn)向簇首發(fā)送數(shù)據(jù)的能耗為

其中Noj為第j個(gè)數(shù)據(jù)轉(zhuǎn)發(fā)簇內(nèi)普通節(jié)點(diǎn)的個(gè)數(shù)。簇首接收數(shù)據(jù)的能耗為

則該數(shù)據(jù)轉(zhuǎn)發(fā)簇總能耗為

一般情況下，普通節(jié)點(diǎn)向簇首發(fā)送的數(shù)據(jù)包相同，設(shè)定為l比特，那么簇首便收到Noj×l比特?cái)?shù)據(jù)，普通節(jié)點(diǎn)的發(fā)送能耗

簇首的接收能耗

數(shù)據(jù)轉(zhuǎn)發(fā)簇總能耗

2.2簇首選擇機(jī)制

選擇簇首是在簇首競(jìng)爭(zhēng)簇中進(jìn)行的，也就是每個(gè)分區(qū)中所有節(jié)點(diǎn)參與競(jìng)爭(zhēng)該分區(qū)的簇首，而分區(qū)節(jié)點(diǎn)數(shù)目固定，由能耗模型可知，普通節(jié)點(diǎn)的能耗取決于距離簇首的距離，簇首的能耗不變，競(jìng)爭(zhēng)簇總能耗取決于普通節(jié)點(diǎn)到簇首的距離平方和。

本協(xié)議所解決的問題在于，一要選擇競(jìng)爭(zhēng)簇中剩余能量較大的節(jié)點(diǎn)作為簇首，二要保證競(jìng)爭(zhēng)簇中節(jié)點(diǎn)能耗均衡，三要保證競(jìng)爭(zhēng)簇總能耗較小。能耗均衡與競(jìng)爭(zhēng)簇總能耗較小與競(jìng)爭(zhēng)簇的拓?fù)浣Y(jié)構(gòu)有關(guān)，當(dāng)節(jié)點(diǎn)隨機(jī)分布后，其位置一般不會(huì)改變，不同的節(jié)點(diǎn)擔(dān)任簇首，就形成了不同的競(jìng)爭(zhēng)簇的拓?fù)浣Y(jié)構(gòu)。

若要保證普通節(jié)點(diǎn)能耗均衡，就是要把普通節(jié)點(diǎn)到簇首的距離的方差限制在一定范圍內(nèi)，而要保證競(jìng)爭(zhēng)簇總能耗較小就要使普通節(jié)點(diǎn)到簇首的距離平方和較小。

在選擇簇首時(shí)，本文綜合考慮簇首的剩余能量，普通節(jié)點(diǎn)到簇首距離的方差和普通節(jié)點(diǎn)到簇首距離的平方和3個(gè)方面，采用下面的3級(jí)簇首選擇機(jī)制：

第1級(jí)：保證簇首的剩余能量較高。將競(jìng)爭(zhēng)簇的節(jié)點(diǎn)按照剩余能量降序排列，設(shè)該競(jìng)爭(zhēng)簇的存活節(jié)點(diǎn)數(shù)目為N1，若1≤N1≤2，則將排在第一的節(jié)點(diǎn)設(shè)置為簇首；若N1≥3，若取出排名前的節(jié)點(diǎn)作為候選簇首，n1∈[2，N1]；

第2級(jí)：保證普通節(jié)點(diǎn)的能耗均衡。第一級(jí)獲取的候選簇首，分別假設(shè)為簇首，求出每個(gè)候選簇首對(duì)應(yīng)的能耗方差，把候選簇首按照方差進(jìn)行升序排序，若N2=2，則將排在第一的候選簇首設(shè)置為簇首，若N2≥3，取出排名前的候選簇首作為待定簇首，n2∈[2，N2]；

第3級(jí)：保證競(jìng)爭(zhēng)簇總能耗較小。分別計(jì)算第二級(jí)獲取的待定簇首為簇首時(shí)對(duì)應(yīng)的總能耗，并將待定簇首按照總能耗進(jìn)行升序排列，取出能耗最小的待定簇首作為該競(jìng)爭(zhēng)簇的簇首。

所采用的3級(jí)簇首選擇機(jī)制，兼顧了簇首剩余能量、普通節(jié)點(diǎn)的能耗均衡、競(jìng)爭(zhēng)簇總能耗3個(gè)方面，但這3個(gè)方面的優(yōu)先程度不同，首先保證簇首剩余能量處于競(jìng)爭(zhēng)簇的較高水平，其次保證待定簇首所對(duì)應(yīng)的能耗方差較小，最后保證所選簇首對(duì)應(yīng)的最小總能耗較小。

3級(jí)簇首選擇機(jī)制在選擇簇首方面十分靈活，它可以通過調(diào)整n1和n2的值，合理地分配給簇首剩余能量、簇內(nèi)節(jié)點(diǎn)能耗均衡和競(jìng)爭(zhēng)簇總能耗相應(yīng)的權(quán)重，從而有利于滿足多種應(yīng)用需求，本文后面的仿真中取n1=n2=2。

3　數(shù)據(jù)轉(zhuǎn)發(fā)

本文提出的路由協(xié)議具有可擴(kuò)展性，這就意味著某一節(jié)點(diǎn)可能距離基站很遠(yuǎn)，直接向基站傳輸數(shù)據(jù)會(huì)產(chǎn)生很大的能耗，因此本協(xié)議采用了3層通信架構(gòu)，即普通節(jié)點(diǎn)到簇首、簇首到簇首和簇首到基站的數(shù)據(jù)轉(zhuǎn)發(fā)［10］。首先，普通節(jié)點(diǎn)將感知的數(shù)據(jù)轉(zhuǎn)發(fā)給距離最近的簇首，然后該簇首對(duì)接收的數(shù)據(jù)進(jìn)行融合后選擇下一跳簇首轉(zhuǎn)發(fā)，最終數(shù)據(jù)會(huì)到達(dá)基站，因此在數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)，如何選擇下一跳簇首則是本文協(xié)議的第3個(gè)關(guān)鍵，本文設(shè)計(jì)了下一跳簇首選擇算法，既均衡了節(jié)點(diǎn)能耗，又減少了網(wǎng)絡(luò)總能耗。

由于節(jié)點(diǎn)的隨機(jī)分布，網(wǎng)絡(luò)數(shù)據(jù)轉(zhuǎn)發(fā)時(shí)會(huì)出現(xiàn)熱區(qū)效應(yīng)，即內(nèi)層節(jié)點(diǎn)能量消耗要比外層節(jié)點(diǎn)要快，之所以出現(xiàn)這種現(xiàn)象，原因在于內(nèi)層簇首不僅要處理簇內(nèi)節(jié)點(diǎn)的數(shù)據(jù)，還要接收、融合、轉(zhuǎn)發(fā)外層簇首轉(zhuǎn)發(fā)來的數(shù)據(jù)。本文提出的下一跳簇首選擇算法，一方面，為了緩解“熱區(qū)效應(yīng)”隔層選擇簇首，確保內(nèi)層節(jié)點(diǎn)的能耗速度不要過快，另一方面，在隔層選擇下一跳簇首上加入d0條件約束，確保隔層節(jié)點(diǎn)的數(shù)據(jù)轉(zhuǎn)發(fā)能耗符合慢衰落能耗模型，減少了能量消耗。

下一跳簇首選擇算法

if S（i）. Energy>0 & S（i）.IsHeader==0//存活著的普通節(jié)點(diǎn)

S（i）. NextHop=min{dis.CHAI，...，dis.CHAVI，dis.CHBI，dis.CHBII，...，dis.CHBXII，...，dis.CHDXII}

//選擇距離最近的簇首作為數(shù)據(jù)轉(zhuǎn)發(fā)的下一跳節(jié)點(diǎn)

else if S（i）. IsHeader==1//簇首節(jié)點(diǎn)

if S（i）. Layer==D//該簇首節(jié)點(diǎn)位于D層

if min{dis.CHBI，dis.CHBII，...，dis.CHBXII}

//該簇首節(jié)點(diǎn)距B層簇首節(jié)點(diǎn)的最小距離小于等于d0

S

（i）. NextHop=min{dis.CHBI，dis.CHBII，...，dis.CHBXII}

//選擇距離該簇首最近的B層簇首作為數(shù)據(jù)轉(zhuǎn)發(fā)的下點(diǎn)

else

S（i）. NextHop=min{dis.CHCI，dis.CHCII，...，dis.CHCXII}

//選擇距離該簇首最近C層簇首作為數(shù)據(jù)轉(zhuǎn)發(fā)的下一跳節(jié)點(diǎn)

if S（i）. NextHop==0//C層傳感節(jié)點(diǎn)全部死亡

S（i）. NextHop=min{dis.CHBI，dis.CHBII，...，dis.CHBXII}

//選擇距離該簇首最近B層簇首作為數(shù)據(jù)轉(zhuǎn)發(fā)的下一跳節(jié)點(diǎn)

endif

if S（i）. NextHop==0//B層傳感節(jié)點(diǎn)全部死亡

S（i）. NextHop=min{dis.CHAI，dis.CHAII，...，dis.CHAVI}

//選擇距離該簇首最近B層簇首作為數(shù)據(jù)轉(zhuǎn)發(fā)的下一跳節(jié)點(diǎn)

endif

if S（i）. NextHop==0//A層傳感節(jié)點(diǎn)全部死亡

S

（i）. NextHop=BS//傳輸數(shù)據(jù)直接送基站

endif

endif

endif

if S（i）. Layer==C

if min{dis.CHAI，dis.CHAII，...，dis.CHAVI}

S（i）. NextHop=min{dis.CHAI，dis.CHAII，...，dis.CHAVI}

else

S（i）. NextHop=min{dis.CHBI，dis.CHBII，...，dis.CHBXII}

if S（i）. NextHop==0

S（i）. NextHop=min{dis.CHAI，dis.CHAII，...，dis.CHAVI}

endif

if S（i）. NextHop==0

S（i）. NextHop=BS

endif

endif

endif

if S（i）. Layer==A|| S（i）. Layer==B

S（i）. NextHop=BS

endif

endif

endif

4　算法仿真分析

本文采用MATLAB對(duì)MEET、DREEM-ME和本文協(xié)議進(jìn)行仿真，在節(jié)點(diǎn)存活數(shù)目、簇首數(shù)據(jù)包接收數(shù)量、網(wǎng)絡(luò)剩余總能量三個(gè)方面進(jìn)行比較，以此檢驗(yàn)本文協(xié)議的性能。在仿真時(shí)，與MEET和DREEM-ME協(xié)議最初均勻分布節(jié)點(diǎn)不同，為更加貼近實(shí)際，本文在三種協(xié)議的仿真中，均使用相同隨機(jī)分布的節(jié)點(diǎn)，同時(shí)擴(kuò)大了最初MEET和DREEMME協(xié)議的仿真規(guī)模。

4.1仿真參數(shù)設(shè)置

仿真是在相同的隨機(jī)節(jié)點(diǎn)分布、相同的數(shù)據(jù)包大小、相同的能耗模型等的基礎(chǔ)上，分別采用MEET、DREEM-ME和本文協(xié)議，創(chuàng)造路由協(xié)議仿真的唯一差異性，從而使仿真結(jié)果具有很強(qiáng)的說服力，具體仿真參數(shù)設(shè)置如表1所示。

表1　協(xié)議仿真相關(guān)參數(shù)設(shè)置

4.2仿真結(jié)果

4.2.1網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)量

穩(wěn)定期是以網(wǎng)絡(luò)第一個(gè)節(jié)點(diǎn)死亡的時(shí)間計(jì)算，如圖5所示，本文協(xié)議的第一個(gè)死亡節(jié)點(diǎn)是在第425個(gè)周期，而MEET和DREEM-ME協(xié)議第一個(gè)死亡節(jié)點(diǎn)則分別在第4個(gè)和第10個(gè)周期。顯而易見，在保持網(wǎng)絡(luò)的穩(wěn)定性上，本文協(xié)議要遠(yuǎn)比MEET 和DREEM-ME協(xié)議優(yōu)越。

就所有節(jié)點(diǎn)死亡的時(shí)間看，MEET和DREEMME協(xié)議相同，比本文協(xié)議要長(zhǎng)。在第1600個(gè)周期時(shí)，三種協(xié)議的存活節(jié)點(diǎn)數(shù)量相近，約有30個(gè)，約占總節(jié)點(diǎn)的6%，并且主要分布在基站附近，覆蓋面積極小，從某種程度上可以說，網(wǎng)絡(luò)有效壽命已盡，這說明了同MEET和DREEM-ME協(xié)議相比，本文協(xié)議基本上不改變網(wǎng)絡(luò)有效生存期。

圖5　網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)量對(duì)比

4.2.2簇頭接收的數(shù)據(jù)包

如圖6所示，MEET和DREEM-ME協(xié)議分別在1096個(gè)周期、1105個(gè)周期后就只剩下直接與基站進(jìn)行通信的節(jié)點(diǎn)，而本文協(xié)議在1871個(gè)周期后才只剩下直接與基站通信的節(jié)點(diǎn)，這都說明了在整個(gè)網(wǎng)絡(luò)的有效生存期內(nèi)，本文協(xié)議簇頭接收的數(shù)據(jù)包數(shù)量要遠(yuǎn)大于MEET和DREEM-ME協(xié)議，通常簇頭接收的數(shù)據(jù)包越多，越表明網(wǎng)絡(luò)的有效監(jiān)測(cè)覆蓋率就越大，網(wǎng)絡(luò)的服務(wù)水平就越高。

圖6　簇頭接收的數(shù)據(jù)包對(duì)比

4.2.3網(wǎng)絡(luò)剩余能量

如圖7所示，在整個(gè)網(wǎng)絡(luò)有效生命期間內(nèi)，本文協(xié)議的網(wǎng)絡(luò)剩余能量要大于MEET和DREEMME協(xié)議，說明了本文協(xié)議在節(jié)省網(wǎng)絡(luò)總能耗方面要優(yōu)于MEET和DREEM-ME協(xié)議，這對(duì)于提高網(wǎng)絡(luò)的服務(wù)質(zhì)量很有幫助。

圖7　網(wǎng)絡(luò)剩余能量對(duì)比

5　結(jié)論

為了能夠使網(wǎng)絡(luò)節(jié)點(diǎn)能耗均衡，增強(qiáng)網(wǎng)絡(luò)穩(wěn)定性，提高網(wǎng)絡(luò)服務(wù)水平，本文提出了更加優(yōu)化的分區(qū)算法、三級(jí)簇首選擇機(jī)制和下一跳簇首選擇算法。其中，分區(qū)算法解決了網(wǎng)絡(luò)中簇首分布隨機(jī)性的問題，使得簇首均勻分布在整個(gè)區(qū)域范圍內(nèi)；三級(jí)簇首選擇機(jī)制，綜合考慮了節(jié)點(diǎn)剩余能量、簇內(nèi)節(jié)點(diǎn)能耗均衡、簇內(nèi)部總消耗三個(gè)方面，選出的簇首既有利于均衡網(wǎng)絡(luò)節(jié)點(diǎn)的能耗，同時(shí)在一定程度上可以減小總的網(wǎng)絡(luò)能耗；下一跳簇首選擇算法，則用來解決距離基站較遠(yuǎn)的節(jié)點(diǎn)通過多跳的方式向基站傳輸數(shù)據(jù)，緩解了網(wǎng)絡(luò)的熱區(qū)效應(yīng)。

對(duì)本文的路由協(xié)議進(jìn)行了MATLAB仿真，評(píng)價(jià)其相關(guān)指標(biāo)，并將其與MEET和DREEM-ME協(xié)議進(jìn)行對(duì)比，仿真結(jié)果表明，在網(wǎng)絡(luò)存活節(jié)點(diǎn)、簇頭接收的數(shù)據(jù)包數(shù)量和網(wǎng)絡(luò)剩余能量等方面，基于分區(qū)的能耗均衡路由協(xié)議要明顯優(yōu)于MEET和DREEM-ME協(xié)議。

參考文獻(xiàn)：

［1］許韻.無線傳感器網(wǎng)絡(luò)中層次型鏈?zhǔn)铰酚蓞f(xié)議的研究［D］.安徽：安徽大學(xué)，2011.

［2］Heinzelman W R，Chandrakasan A，Balakrishnan H. Energy-Effi?cient Communication Protocol for Wireless Microsensor Networks ［C］//Proceedings of the 33rd Hawaii International Conference on System Sciences，2000. IEEE，2000：10.

［3］曹建玲，劉文朋，彭雙，等.一種基于能耗均衡的ZigBee網(wǎng)絡(luò)高效混合路由算法［J］.電訊技術(shù)，2013，53（10）：1352-1356.

［4］董亮，張靈，陳云華.基于限制廣播的ZigBee分布式動(dòng)態(tài)能量均衡協(xié)議［J］.傳感技術(shù)學(xué)報(bào)，2014，27（8）：1120-1124.

［5］何杏宇，周亦敏，楊桂松，等.無線傳感器網(wǎng)絡(luò)能量感知增強(qiáng)樹型路由協(xié)議研究［J］.傳感技術(shù)學(xué)報(bào)，2015，28（4）：551-556.

［6］劉慶，王培康.無線傳感器網(wǎng)絡(luò)的安全分簇路由協(xié)議［J］.計(jì)算機(jī)仿真，2009，26（4）：167-171.

［7］張文祥，馬銀花，郭繼坤.無線傳感器網(wǎng)絡(luò)路由算法的研究［J］.計(jì)算機(jī)測(cè)量與控制，2009，17（3）：617-619.

［8］童夢(mèng)軍，關(guān)華丞.基于蟻群算法的能量均衡多路徑路由算法的研究［J］.傳感技術(shù)學(xué)報(bào)，2013，26（3）：425-434.

［9］Saleem F，Javaid N，Moeen Y，et al. MEET：Multi-Hop Energy Ef?ficient Protocol for Energy Hole Avoidance using Variable Trans?mission Range in Wireless Sensor Networks［C］//9th International Conference on Broadband and Wireless Computing，Communica?tion and Applications. IEEE. 2014：478-484.

［10］Amjad N，Javaid N，Haider A，et al. DREEM-ME：Distributed Re?gional Energy Efficient Multi-Hop Routing Protocol based on Max?imum Energy in WSN［C］//8th International Conference on Broad?band and Wireless Computing，Communication and Applications. IEEE. 2013：43-48.

［11］Ahmad A，Latif K，Javaid N，et al. Density Controlled Divide-and-Rule Scheme for Energy Efficient Routing in wireless sensor net?works［C］// 26th IEEE Canadian Conference Of Electrical And Computer Engineering（CCECE）. IEEE. 2013：1-4.

［12］唐毅，梁曉曦，武俊.無線傳感器網(wǎng)絡(luò)最優(yōu)簇首節(jié)點(diǎn)數(shù)量研究［J］.通信技術(shù)，2007（6）：30-32.

［13］盧翔，涂時(shí)亮，陳章龍.對(duì)無線傳感器網(wǎng)絡(luò)定位算法的比較和分析［J］.計(jì)算機(jī)應(yīng)用與軟件，2009，26（12）：199-201，285.

翟春杰（1989-），男，安徽亳州，碩士研究生，主要研究領(lǐng)域?yàn)橹悄芸刂评碚撆c應(yīng)用，auchunjiezhai@mail.scut.edu.cn；

劉永桂（1978-），男，湖南邵陽，博士，副教授，主要研究領(lǐng)域?yàn)闊o線傳感器網(wǎng)絡(luò)，auygliu@scut.edu.cn。

徐建閩（1960-），男，山東招遠(yuǎn)，博士，教授，博士生導(dǎo)師，主要研究領(lǐng)域?yàn)橹悄芸刂评碚撆c應(yīng)用、交通信息工程及控制、智能交通系統(tǒng)等，aujmxu@scut.edu.cn；

Minimum Transmit Power Based Distributed Relay Selection in Wireless Networks*

WU Hang1，QIAN Liping1*，CHEN Qingzhang1，LU Weidang2
（1.College of Computer Science and Technology，Zhejiang University of Technology，Hangzhou 310023，China；2.College of Information Engineering，Zhejiang University of Technology，Hangzhou 310023，China）

Abstract：Relay cooperation has been proposed as a promising solution to improve the energy efficiency and service quality of edge users. In this regard，this work proposes a distributed auction-based relay selection algorithm to mini?mize the total transmit power consumption for dual-hop decode-and-forward relay networks over Rayleigh fading channels. In particular，we first provide the optimal power consumption of any cooperative transmission in the closed-form expression. Then，we design a distributed relay selection algorithm that assigns every user to the appro?priate relay node based on the idea of auction. Simulation results show that every user node can find its best coopera?tive relay through limited message passing with relay nodes.

Key words：wireless network；relay selection；auction algorithm；multi-user multi-relay

doi：EEACC：6150P10.3969/j.issn.1004-1699.2016.01.016

收稿日期：2015-08-13修改日期：2015-10-12

中圖分類號(hào)：TN92

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-1699（2016）01-0080-08

項(xiàng)目來源：國(guó)家自然科學(xué)基金項(xiàng)目（61573153）；廣州市科技計(jì)劃項(xiàng)目（201510010132）