張雁東, 趙宏偉, 王出航, 楊興旺

(1. 吉林省教育廳 教育科技產(chǎn)業(yè)服務(wù)中心, 長(zhǎng)春 130022； 2. 吉林大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長(zhǎng)春 130012；3. 長(zhǎng)春師范大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 長(zhǎng)春 130032； 4. 長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院, 長(zhǎng)春 130012)

0 引 言

近年來, 無線傳感器網(wǎng)絡(luò)在軍事、 森林防火、 海洋監(jiān)控等方面得到了廣泛應(yīng)用[1-3]。但由于受部署環(huán)境、 地理位置、 部署成本等因素影響, 如何對(duì)傳感器網(wǎng)絡(luò)中有限的能量進(jìn)行充分利用, 延長(zhǎng)網(wǎng)絡(luò)工作壽命成為傳感器網(wǎng)絡(luò)的研究重點(diǎn), 分簇路由算法被證明是一種十分有效的方法[4-10]。

Heinzelman等[4]最早提出了一種典型的網(wǎng)絡(luò)分簇路由算法, 其核心思想是在網(wǎng)絡(luò)中節(jié)點(diǎn)通過選擇0～1之間的隨機(jī)數(shù)決定是否成為簇頭, 根據(jù)所選簇頭對(duì)網(wǎng)絡(luò)分簇。通過簇頭收集簇內(nèi)節(jié)點(diǎn)的信息, 并將數(shù)據(jù)信息進(jìn)行處理融合后發(fā)送至匯聚節(jié)點(diǎn), 該算法減少了其他節(jié)點(diǎn)與基站間的直接通信, 降低了能量的消耗。李建坡等[5]提出了一種基于能量迭代的非均勻分簇路由算法, 該算法在簇頭選舉時(shí)通過減少迭代次數(shù)以達(dá)到降低能量消耗的目的, 同時(shí)綜合考慮節(jié)點(diǎn)能耗速度、 節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離等因素, 選出最優(yōu)簇頭。Yadav等[6]提出了一種改進(jìn)的LEACH算法LEACH-R, 它在簇頭選舉過程綜合考慮節(jié)點(diǎn)能量、 距離、 分布密度等因素選取更加合理的簇頭, 同時(shí)對(duì)簇的大小進(jìn)行優(yōu)化, 使簇頭能耗更加均衡, 但該算法傳輸方式使用簇頭與基站直接通信的方式, 這使傳輸路徑加長(zhǎng), 使傳輸能耗過大而易出現(xiàn)能量空洞問題。蔣暢江等[7]提出了采用基于時(shí)間的簇頭競(jìng)爭(zhēng)的非均勻分簇算法, 減小基站附近節(jié)點(diǎn)的成簇半徑實(shí)現(xiàn)網(wǎng)絡(luò)能量的均衡。Batra等[8]提出了一種改進(jìn)的LEACH-MAC協(xié)議, 將該協(xié)議穩(wěn)定了每輪所選出的簇頭個(gè)數(shù), 避免了LEACH協(xié)議每輪選舉簇頭數(shù)的隨機(jī)性。張長(zhǎng)森等[9]提出了一種能量高效的非均勻分簇算法(EUCA： Energy-efficient Uneven Clustering Algorithm), 該算法針對(duì)LEACH算法中的簇頭選擇機(jī)制進(jìn)行了改進(jìn), 提出了基于節(jié)點(diǎn)剩余能量的簇頭選舉策略, 并且對(duì)EEUC算法的成簇半徑和簇間路由進(jìn)行了改進(jìn), 達(dá)到延長(zhǎng)網(wǎng)絡(luò)周期的效果。Pant等[10]提出了一種多跳分簇路由算法Multi-hop EEBCDA, 它將網(wǎng)絡(luò)劃分為不同的網(wǎng)格, 使遠(yuǎn)離匯聚節(jié)點(diǎn)位置的簇規(guī)模更大、 節(jié)點(diǎn)更多, 簇頭采用多跳方式傳輸數(shù)據(jù), 但該算法沒有考慮多跳傳輸時(shí)的中繼節(jié)點(diǎn)的剩余能量, 會(huì)導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗不均勻而產(chǎn)生能量空洞等問題。

針對(duì)上述問題, 筆者提出基于模糊控制的環(huán)形無線傳感器網(wǎng)絡(luò)多跳分簇路由算法(FCRA: Fuzzy logic control based Clustering Routing Algorithm)。首先將網(wǎng)絡(luò)分為間距相等的若干圓環(huán), 以每環(huán)能耗最小為原則, 計(jì)算出每個(gè)圓環(huán)中的最佳簇頭數(shù)目； 然后, 在成簇階段運(yùn)用模糊控制的方法選舉每個(gè)簇的簇頭, 避免了由于隨機(jī)選舉簇頭導(dǎo)致環(huán)內(nèi)簇頭分布不均勻而造成的網(wǎng)絡(luò)負(fù)載不均衡等問題； 最后, 簇間的路由方式根據(jù)數(shù)據(jù)包長(zhǎng)度、 下一節(jié)點(diǎn)的剩余能量以及簇間通信消耗有機(jī)的結(jié)合, 計(jì)算每條傳輸路徑的權(quán)重函數(shù), 選擇權(quán)重函數(shù)小的路徑進(jìn)行數(shù)據(jù)傳輸。

1 系統(tǒng)模型

1.1 網(wǎng)絡(luò)模型

圖1 網(wǎng)絡(luò)模型Fig.1 Network model

將網(wǎng)絡(luò)模型等效為以R為半徑的圓形區(qū)域, 將其分成n個(gè)以ri(從內(nèi)向外i=1,…,n)為間距的同心圓中,N個(gè)節(jié)點(diǎn)均勻分布在該圓形區(qū)域中, 匯聚節(jié)點(diǎn)SINK在圓心的位置[11]。并且假設(shè)：

1) 每個(gè)節(jié)點(diǎn)具有唯一的ID, 均勻分布在網(wǎng)絡(luò)中；

2) 所有節(jié)點(diǎn)位置固定且能量有限, 但對(duì)匯聚節(jié)點(diǎn)能量沒有限制；

3) 所有節(jié)點(diǎn)都具有相似的能力, 都能當(dāng)簇頭節(jié)點(diǎn)或普通節(jié)點(diǎn)；

4) 節(jié)點(diǎn)間可以相互通信, 可以通過接受消息的信號(hào)強(qiáng)度計(jì)算二者的距離。

1.2 能量模型

數(shù)據(jù)傳輸能耗采用文獻(xiàn)[12-13]中模型, 節(jié)點(diǎn)發(fā)送數(shù)據(jù)消耗的能量為

(1)

(2)

其中l(wèi)為數(shù)據(jù)長(zhǎng)度；Eelec為收發(fā)電路的功耗系數(shù)；d為通信距離；d0為自由空間傳輸模型與多徑衰減傳輸模型的臨界值。當(dāng)d

節(jié)點(diǎn)接收數(shù)據(jù)消耗的能量可表示為

Erx(l,d)=lEelec

(3)

節(jié)點(diǎn)進(jìn)行數(shù)據(jù)融合消耗的能量可表示為

EA=lEDA

(4)

每個(gè)節(jié)點(diǎn)固定的能量消耗可表示為

Eid=Eelec

(5)

2 算法設(shè)計(jì)

首先對(duì)網(wǎng)絡(luò)初始化, 由匯聚節(jié)點(diǎn)向網(wǎng)絡(luò)中節(jié)點(diǎn)發(fā)布網(wǎng)絡(luò)的整體消息ADV_SINK_MSG, 網(wǎng)絡(luò)中節(jié)點(diǎn)根據(jù)接收到消息的信號(hào)強(qiáng)度判斷自身位置。在網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)都確定好自身的信息后, 進(jìn)入網(wǎng)絡(luò)的工作階段, 網(wǎng)絡(luò)的工作階段大致可以分成兩個(gè)階段： 成簇階段以及數(shù)據(jù)傳輸?shù)穆酚呻A段。

2.1 成簇階段

2.1.1 最佳簇?cái)?shù)選擇

在每個(gè)簇內(nèi)的節(jié)點(diǎn)能量消耗可以分為兩部分： 簇頭節(jié)點(diǎn)消耗以及簇內(nèi)普通節(jié)點(diǎn)消耗。

第i個(gè)圓環(huán)的節(jié)點(diǎn)數(shù)為

(6)

假設(shè)環(huán)內(nèi)的每個(gè)簇就是以相同半徑的圓覆蓋, 且第i環(huán)的最優(yōu)簇頭數(shù)目為mi。則第i環(huán)內(nèi)節(jié)點(diǎn)與簇頭距離的均值為

(7)

第i環(huán)節(jié)點(diǎn)向簇頭發(fā)送數(shù)據(jù)消耗的能量為

(8)

第i環(huán)簇頭到基站的距離均值的平方為

(9)

第i環(huán)簇頭到基站的距離的均值為

(10)

第i環(huán)簇頭節(jié)點(diǎn)距下一跳簇頭節(jié)點(diǎn)的距離可表示為

(11)

第i環(huán)簇頭消耗的能量為

(12)

第i環(huán)每個(gè)節(jié)點(diǎn)消耗的能量為

Echi-node=lEtx

(13)

一個(gè)簇消耗的能量總和可通過

(14)

計(jì)算得出, 則第i環(huán)消耗的能量為

Etotal=miEclustris=miEchi-head+NiEchi-node

(15)

(16)

(17)

2.1.2 簇頭選舉

在計(jì)算每個(gè)圓環(huán)中的節(jié)點(diǎn)數(shù)目和最佳簇頭數(shù)后, 接下來就是簇頭選舉階段。在傳統(tǒng)方法中, 通常采用嚴(yán)格的隨機(jī)輪轉(zhuǎn)的方式, 但在很大程度上會(huì)使簇頭的選擇具有隨機(jī)性, 會(huì)造成簇頭在某一部分分布的過于密集或稀疏, 從而導(dǎo)致無線傳感器網(wǎng)絡(luò)中的熱點(diǎn)或空洞現(xiàn)象。

為了避免簇頭選擇的隨機(jī)性, 采用模糊控制[14]的方法選擇每個(gè)簇的簇頭。如圖2所示為簇頭選擇的模糊控制器結(jié)構(gòu), 將網(wǎng)絡(luò)中節(jié)點(diǎn)的位置信息以及節(jié)點(diǎn)自身的剩余能量作為模糊控制器的輸入, 輸出為節(jié)點(diǎn)成為簇頭的概率。

圖2 模糊控制器結(jié)構(gòu)Fig.2 Fuzzy controller structure

首先, 輸入節(jié)點(diǎn)的信息, 通過模糊語(yǔ)言及如圖3所示的隸屬函數(shù)對(duì)輸入的消息進(jìn)行模糊化, 其中, 節(jié)點(diǎn)位置的模糊變量為“很遠(yuǎn)(NB)、 遠(yuǎn)(NM)、 較遠(yuǎn)(NS)、 中(M)、 較近(PS)、 近(PM)、 很近(PB)”； 節(jié)點(diǎn)的剩余能量模糊語(yǔ)言變量為“很低(NB)、 低(NM)、 較低(NS)、 中(M)、 較高(PS)、 高(PM)、 很高(PB)”, 模糊控制系統(tǒng)的輸出簇頭概率的模糊語(yǔ)言變量“很小(NB)、 小(NM)、 較小(NS)、 中(M)、 較大(PS)、 大(PM)、 很大(PB)”, 其中“低、 高、 遠(yuǎn)、 近、 很小、 很大”采用梯形隸屬度函數(shù), 其余為三角隸屬度函數(shù)。然后, 根據(jù)表1設(shè)定if-then結(jié)構(gòu)的模糊條件語(yǔ)句構(gòu)成模糊控制規(guī)則, 對(duì)模糊化的數(shù)據(jù)進(jìn)行推理后, 得到模糊控制器的輸出, 模糊推理輸出的是模糊語(yǔ)言變量。最后, 采用質(zhì)心法對(duì)輸出的模糊語(yǔ)言解模糊, 得到簇內(nèi)節(jié)點(diǎn)成為簇頭的概率。

表1 模糊規(guī)則

當(dāng)計(jì)算完成節(jié)點(diǎn)的成簇概率后, 每個(gè)節(jié)點(diǎn)向其鄰居節(jié)點(diǎn)發(fā)送報(bào)文CH_COMPETE_MSG, 包括該節(jié)點(diǎn)的ID、 成簇概率。鄰居節(jié)點(diǎn)接收到報(bào)文后, 更新簇頭列表, 當(dāng)某個(gè)節(jié)點(diǎn)的成簇概率大于其他鄰居節(jié)點(diǎn)時(shí), 該節(jié)點(diǎn)成為簇頭, 其他節(jié)點(diǎn)為候選簇頭。簇頭節(jié)點(diǎn)向其他鄰居節(jié)點(diǎn)廣播CH_SUCCESS_MSG, 其他鄰居節(jié)點(diǎn)根據(jù)接收?qǐng)?bào)文的信號(hào)強(qiáng)度選擇加入最近的簇, 同時(shí)向加入的簇頭發(fā)送加入簇的報(bào)文CH_JOIN_MSG, 構(gòu)成一個(gè)簇。當(dāng)一輪傳輸完成后, 在成簇概率列表中刪除該簇頭, 采用上述方式在候選簇頭中重新競(jìng)選簇頭。

2.2 路由階段

當(dāng)簇建立完成, 簇內(nèi)節(jié)點(diǎn)開始傳輸數(shù)據(jù), 在工作過程中, 簇頭的能量消耗主要用于發(fā)送數(shù)據(jù), 因此為了延長(zhǎng)網(wǎng)絡(luò)的生命周期, 應(yīng)該尋找能量消耗最少的傳輸路徑減少簇頭消耗； 同時(shí)為了使簇頭的能耗均衡, 應(yīng)該綜合考慮傳輸路徑上其他簇頭的剩余能量、 傳輸距離等因素。

文獻(xiàn)[15]中證明了在多跳網(wǎng)絡(luò)中, 當(dāng)每次傳輸?shù)木嚯x相等時(shí), 網(wǎng)絡(luò)消耗的能量最小。由此可得： 在不同情況下, 環(huán)i中簇頭節(jié)點(diǎn)的傳輸情況可通過

S(i)=「log2i?+1

(18)

確定。用H(k)表示簇頭在每種情況下的多跳數(shù), 每種情況下的多跳數(shù)可通過

(19)

計(jì)算得到。當(dāng)采用不同的傳輸方法,H(k)下一跳的環(huán)數(shù)可由

(20)

算出。為了節(jié)省能量, 假設(shè)在不進(jìn)行數(shù)據(jù)傳輸時(shí), 簇頭點(diǎn)處于休眠狀態(tài)。對(duì)剩余的簇頭節(jié)點(diǎn), 通過

(21)

算出其每條傳輸路徑的權(quán)重函數(shù)gi。其中c1、c2、c3、c4為每條路徑的加權(quán)因子,r為當(dāng)前網(wǎng)絡(luò)工作的輪數(shù),Nres為下一跳所在環(huán)的第r輪存活節(jié)點(diǎn)數(shù),Nint為下一跳節(jié)點(diǎn)所在環(huán)的初始節(jié)點(diǎn)數(shù),dhop為簇頭節(jié)點(diǎn)下一跳傳輸?shù)木嚯x,dmax為網(wǎng)絡(luò)中節(jié)點(diǎn)距匯聚節(jié)點(diǎn)的最遠(yuǎn)距離,Eint為節(jié)點(diǎn)的初始能量,Eres為節(jié)點(diǎn)的剩余能量,H(k)為節(jié)點(diǎn)i將數(shù)據(jù)傳輸?shù)絽R聚節(jié)點(diǎn)的跳數(shù),Eid為每個(gè)節(jié)點(diǎn)的固定消耗。

式(21)中, 第1項(xiàng)主要考慮網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目會(huì)隨著網(wǎng)絡(luò)工作時(shí)間的增加而減少, 當(dāng)轉(zhuǎn)發(fā)上一簇頭節(jié)點(diǎn)的數(shù)據(jù)時(shí), 節(jié)點(diǎn)越多會(huì)使簇頭消耗的能量越多, 權(quán)重函數(shù)越大； 第2項(xiàng)考慮了下一簇頭節(jié)點(diǎn)的剩余能量, 當(dāng)下一簇頭節(jié)點(diǎn)剩余能量越少, 可用于轉(zhuǎn)發(fā)的能量就越少, 權(quán)重函數(shù)就越大； 第3項(xiàng)主要考慮每跳傳輸?shù)木嚯x, 當(dāng)傳輸距離較大時(shí), 能量消耗的越大, 權(quán)重函數(shù)就越大； 第4項(xiàng)主要考慮由于簇頭節(jié)點(diǎn)傳輸數(shù)據(jù)可以采用多種情況, 但只考慮傳輸距離會(huì)使每次都是傳輸路徑最短的是最佳傳輸方式, 所以要結(jié)合該傳輸距離情況下的跳數(shù)； 第5項(xiàng)是簇頭節(jié)點(diǎn)的固定消耗。

由于傳輸時(shí)消耗了能量, 簇頭節(jié)點(diǎn)的剩余能量發(fā)生了變化, 所以在每輪傳輸后要重新計(jì)算每條傳輸路徑的權(quán)重函數(shù)。

具體的算法流程如下。

1) 分簇完成后, 各簇頭節(jié)點(diǎn)根據(jù)式(18)～式(20)計(jì)算該節(jié)點(diǎn)向匯聚節(jié)點(diǎn)的傳輸情況, 不同情況下的傳輸跳數(shù), 以及下一跳節(jié)點(diǎn)所在的環(huán)數(shù)。

2) 當(dāng)簇頭要向匯聚節(jié)點(diǎn)發(fā)送信息時(shí), 根據(jù)步驟1)中計(jì)算的結(jié)果, 尋找到它的所有情況下的下一跳的簇頭節(jié)點(diǎn), 并向該節(jié)點(diǎn)廣播報(bào)文EDGE_HEADNDE_MSG。

3) 當(dāng)下一跳簇頭節(jié)點(diǎn)接收到報(bào)文后, 向該簇頭節(jié)點(diǎn)廣播報(bào)文NEXT_HEADNODE_MSG, 包括自身位置以及剩余能量。

4) 簇頭節(jié)點(diǎn)根據(jù)接收到的NEXT_HEADNODE_MSG消息, 根據(jù)式(21)計(jì)算該條路徑的權(quán)重函數(shù)gi, 并與其他路徑的權(quán)重函數(shù)相比較, 選擇gi值最小的路徑進(jìn)行數(shù)據(jù)傳輸。

5) 在計(jì)算下一跳時(shí), 重復(fù)2)～4)步, 直至下一跳節(jié)點(diǎn)是匯聚節(jié)點(diǎn)為止。

按照尋找到的路徑進(jìn)行數(shù)據(jù)傳輸, 即可實(shí)現(xiàn)簇頭的能量消耗最小。其他環(huán)的簇頭節(jié)點(diǎn)同樣可以通過上述步驟獲得最佳傳輸路徑。

3 仿真分析

為了驗(yàn)證筆者算法FCRA的有效性, 將其與文獻(xiàn)[4]中的LEACH算法和文獻(xiàn)[8]中的Multi-hop EEBCDA算法進(jìn)行比較, 主要比較了網(wǎng)絡(luò)的生存周期及剩余能量。仿真參數(shù)如表2所示。

表2 仿真參數(shù)

3.1 網(wǎng)絡(luò)節(jié)點(diǎn)生存情況

網(wǎng)絡(luò)輪數(shù)與網(wǎng)絡(luò)中存活節(jié)點(diǎn)個(gè)數(shù)的關(guān)系如圖4所示。LEACH算法在602輪出現(xiàn)第1個(gè)死亡節(jié)點(diǎn), 在1 084輪所有節(jié)點(diǎn)全部死亡, 這是由于簇頭節(jié)點(diǎn)直接將數(shù)據(jù)傳輸給網(wǎng)絡(luò)中的匯聚節(jié)點(diǎn), 節(jié)點(diǎn)消耗過多的能量, 導(dǎo)致網(wǎng)絡(luò)死亡過快。Multi-hop EEBCDA算法第1個(gè)死亡節(jié)點(diǎn)出現(xiàn)在747輪, 在1 127輪全部死亡, 這是由于簇頭通過多跳數(shù)據(jù)傳送, 但沒有考慮下一跳節(jié)點(diǎn)是否有足夠的能量接受和發(fā)送數(shù)據(jù), 導(dǎo)致節(jié)點(diǎn)的能量消耗不均勻。FCRA算法在956輪出現(xiàn)死亡節(jié)點(diǎn), 在1 354輪全部死亡, 與LEACH算法相比, 網(wǎng)絡(luò)的使用壽命延長(zhǎng)了24.9%, 證明了FCRA算法相比于傳統(tǒng)算法可以更好的減少網(wǎng)絡(luò)的能量消耗, 延長(zhǎng)了節(jié)點(diǎn)的工作時(shí)間。

圖4 網(wǎng)絡(luò)壽命對(duì)比 圖5 網(wǎng)絡(luò)剩余能量對(duì)比 Fig.4 Comparison of network lifetime Fig.5 Comparison of residual energy

3.2 網(wǎng)絡(luò)能耗情況

網(wǎng)絡(luò)輪數(shù)與網(wǎng)絡(luò)節(jié)點(diǎn)剩余能量的關(guān)系如圖5所示?？梢钥闯? 當(dāng)網(wǎng)絡(luò)中沒有節(jié)點(diǎn)死亡時(shí), LEACH算法、 Multi-hop EEBCDA算法和FCRA算法的能耗比較均勻, 當(dāng)出現(xiàn)死亡節(jié)點(diǎn)時(shí), 3種算法都有不同程度的波動(dòng), FCRA算法在網(wǎng)絡(luò)總體能量消耗上比LEACH算法和Multi-hop EEBCDA算法更節(jié)能。這是由于FCRA算法考慮了節(jié)點(diǎn)在成簇階段和傳輸階段的剩余能量及位置信息, 以降低節(jié)點(diǎn)的能量消耗, 延長(zhǎng)網(wǎng)絡(luò)的壽命, 從而更好地平衡網(wǎng)絡(luò)負(fù)載。

4 結(jié) 語(yǔ)

針對(duì)環(huán)形無線傳感器網(wǎng)絡(luò)的使用壽命問題, 提出了一種新的基于模糊控制的多跳路由算法(FCRA), 該算法先計(jì)算每個(gè)網(wǎng)絡(luò)中的最佳簇?cái)?shù)。在成簇階段, 利用網(wǎng)絡(luò)節(jié)點(diǎn)的剩余能量、 到匯聚節(jié)點(diǎn)的距離作為輸入模糊控制器的參數(shù), 結(jié)合最佳簇?cái)?shù), 選舉網(wǎng)絡(luò)中的最佳簇頭節(jié)點(diǎn)。在傳輸數(shù)據(jù)階段, 采用等間距的多跳路由方式, 由于節(jié)點(diǎn)位置不同, 多跳路徑也不同, 給每條路徑賦予一個(gè)權(quán)值。該權(quán)值主要通過下一跳節(jié)點(diǎn)的剩余能量、 距離以及網(wǎng)絡(luò)中剩余節(jié)點(diǎn)個(gè)數(shù)確定, 選擇權(quán)值最小的路徑進(jìn)行傳輸。仿真結(jié)果表明, FCRA相比LEACH和Multi-hop EEBCDA有更小的能量消耗, 從而提高網(wǎng)絡(luò)的生命周期。