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

(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 引 言

近年來(lái), 無(wú)線傳感器網(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)通過(guò)選擇0～1之間的隨機(jī)數(shù)決定是否成為簇頭, 根據(jù)所選簇頭對(duì)網(wǎng)絡(luò)分簇。通過(guò)簇頭收集簇內(nèi)節(jié)點(diǎn)的信息, 并將數(shù)據(jù)信息進(jìn)行處理融合后發(fā)送至匯聚節(jié)點(diǎn), 該算法減少了其他節(jié)點(diǎn)與基站間的直接通信, 降低了能量的消耗。李建坡等[5]提出了一種基于能量迭代的非均勻分簇路由算法, 該算法在簇頭選舉時(shí)通過(guò)減少迭代次數(shù)以達(dá)到降低能量消耗的目的, 同時(shí)綜合考慮節(jié)點(diǎn)能耗速度、 節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的距離等因素, 選出最優(yōu)簇頭。Yadav等[6]提出了一種改進(jìn)的LEACH算法LEACH-R, 它在簇頭選舉過(guò)程綜合考慮節(jié)點(diǎn)能量、 距離、 分布密度等因素選取更加合理的簇頭, 同時(shí)對(duì)簇的大小進(jìn)行優(yōu)化, 使簇頭能耗更加均衡, 但該算法傳輸方式使用簇頭與基站直接通信的方式, 這使傳輸路徑加長(zhǎng), 使傳輸能耗過(guò)大而易出現(xiàn)能量空洞問(wè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ù), 但該算法沒(méi)有考慮多跳傳輸時(shí)的中繼節(jié)點(diǎn)的剩余能量, 會(huì)導(dǎo)致網(wǎng)絡(luò)節(jié)點(diǎn)能量消耗不均勻而產(chǎn)生能量空洞等問(wèn)題。

針對(duì)上述問(wèn)題, 筆者提出基于模糊控制的環(huán)形無(wú)線傳感器網(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ù)載不均衡等問(wèn)題； 最后, 簇間的路由方式根據(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)能量沒(méi)有限制；

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

4) 節(jié)點(diǎn)間可以相互通信, 可以通過(guò)接受消息的信號(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è)簇消耗的能量總和可通過(guò)

(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ù)后, 接下來(lái)就是簇頭選舉階段。在傳統(tǒng)方法中, 通常采用嚴(yán)格的隨機(jī)輪轉(zhuǎn)的方式, 但在很大程度上會(huì)使簇頭的選擇具有隨機(jī)性, 會(huì)造成簇頭在某一部分分布的過(guò)于密集或稀疏, 從而導(dǎo)致無(wú)線傳感器網(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)的信息, 通過(guò)模糊語(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)開(kāi)始傳輸數(shù)據(jù), 在工作過(guò)程中, 簇頭的能量消耗主要用于發(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)的傳輸情況可通過(guò)

S(i)=「log2i?+1

(18)

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

(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), 通過(guò)

(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)同樣可以通過(guò)上述步驟獲得最佳傳輸路徑。

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)消耗過(guò)多的能量, 導(dǎo)致網(wǎng)絡(luò)死亡過(guò)快。Multi-hop EEBCDA算法第1個(gè)死亡節(jié)點(diǎn)出現(xiàn)在747輪, 在1 127輪全部死亡, 這是由于簇頭通過(guò)多跳數(shù)據(jù)傳送, 但沒(méi)有考慮下一跳節(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ò)中沒(méi)有節(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ú)線傳感器網(wǎng)絡(luò)的使用壽命問(wèn)題, 提出了一種新的基于模糊控制的多跳路由算法(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)值主要通過(guò)下一跳節(jié)點(diǎn)的剩余能量、 距離以及網(wǎng)絡(luò)中剩余節(jié)點(diǎn)個(gè)數(shù)確定, 選擇權(quán)值最小的路徑進(jìn)行傳輸。仿真結(jié)果表明, FCRA相比LEACH和Multi-hop EEBCDA有更小的能量消耗, 從而提高網(wǎng)絡(luò)的生命周期。