基于FCM的無線傳感器網(wǎng)絡(luò)分簇多跳路由算法

楊友良，李艷輝

（河北聯(lián)合大學(xué)，河北 唐山063009）

無線傳感器網(wǎng)絡(luò)通過大量布置在檢測區(qū)域內(nèi)的傳感器節(jié)點(diǎn)采集網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)感知對象的信息，通過多跳的無線通信方式，將收集、處理后的信息提供給終端用戶。由于傳感器節(jié)點(diǎn)本身資源的限制，特別是WSN節(jié)點(diǎn)能量更為有限，因此研究分簇算法是必要的，LEACH算法［1］是最早提出的單跳分簇算法，其在無線傳感器網(wǎng)絡(luò)中占有舉足輕重的作用。然而，為了能夠更加有效的延長網(wǎng)絡(luò)生命周期，我們必須研究新的分簇路由算法。

1 LEACH算法原理

無線傳感器網(wǎng)絡(luò)中的層次路由協(xié)議最大的特點(diǎn)便是采用分簇技術(shù)。利用此技術(shù)可以很明顯的將整個(gè)網(wǎng)絡(luò)內(nèi)的所有節(jié)點(diǎn)分成簇首、簇內(nèi)節(jié)點(diǎn)、匯聚節(jié)點(diǎn)三個(gè)層次［2］。其結(jié)構(gòu)可表示為如圖1所示。LEACH協(xié)議是由Heinzelman提出的層次型路由協(xié)議算法，其在無線傳感器網(wǎng)絡(luò)中占有舉足輕重的作用。針對簇首過重的負(fù)擔(dān)導(dǎo)致其很快失效這一問題，LEACH協(xié)議通過輪次的方法周期性的選擇簇首。一旦節(jié)點(diǎn)成為簇首節(jié)點(diǎn)，它將會(huì)向整個(gè)網(wǎng)絡(luò)廣播其成為簇首的信息，傳感器網(wǎng)絡(luò)中的其它節(jié)點(diǎn)接收到整個(gè)網(wǎng)絡(luò)中所有簇首的信息后，依據(jù)接收信息的信號(hào)強(qiáng)度，挑選出最強(qiáng)的簇首所在簇群加入。在進(jìn)行數(shù)據(jù)信息通訊時(shí)，簇首、簇內(nèi)節(jié)點(diǎn)、數(shù)據(jù)匯聚點(diǎn)三者之間的通訊采用單一的直接通訊方式，即簇首與簇內(nèi)節(jié)點(diǎn)直接傳送信息，簇首與數(shù)據(jù)匯聚點(diǎn)之間也是采用單跳的方式進(jìn)行通訊。

圖1 分簇結(jié)構(gòu)示意圖

LEACH算法中采用以下策略選擇簇首［3］：

數(shù)據(jù)匯集點(diǎn)首先設(shè)定一個(gè)閾值T（n），此閾值決定哪個(gè)傳感器節(jié)點(diǎn)成為簇首，并且，此閾值分配給每一個(gè)傳感器節(jié)點(diǎn)，隨著LEACH算法的運(yùn)行，每個(gè)傳感器節(jié)點(diǎn)的閾值也將隨著改變。閾值T（n）表示如下：

其中，分子P表示在本輪中當(dāng)選簇首在整個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的比例，r表示為當(dāng)前進(jìn)行的輪數(shù)，rmod（1／p）表示為本輪中被選為簇首的個(gè)數(shù)，G表示為本輪中沒有被選擇成為簇首的其它傳感器節(jié)點(diǎn)的集合。當(dāng)本輪建簇開始時(shí)，網(wǎng)絡(luò)中所有的傳感器節(jié)點(diǎn)均需要產(chǎn)生一個(gè)隨機(jī)數(shù)M（〈0〈M〈1），M的意義可以表示如下：

在LEACH算法中，每一輪開始時(shí)都將進(jìn)行簇首的選擇。為了更好地延長網(wǎng)絡(luò)的生存周期，在選擇簇首時(shí)應(yīng)該盡量選擇剩余能量充足的傳感器節(jié)點(diǎn)。但此算法還是有很多不足，所以提出新的算法是有必要的。

3 基于FCM的分簇多跳路由算法

傳統(tǒng)的分簇協(xié)議在確定簇首后，依據(jù)傳感器節(jié)點(diǎn)與簇首的距離進(jìn)行分簇。本文提出的分簇路由協(xié)議首先確立簇群的方位，依據(jù)此方位信息確立簇首及候選族首，保證了整個(gè)網(wǎng)絡(luò)中簇群的均勾分布。

文獻(xiàn)［4］中提到，在實(shí)踐運(yùn)用中，為達(dá)到網(wǎng)絡(luò)無縫覆蓋率η，在監(jiān)測區(qū)域A中隨機(jī)選取的簇首數(shù)K應(yīng)該為：

其中r為節(jié)點(diǎn)傳輸半徑。

當(dāng)節(jié)點(diǎn)由于能量消耗殆盡導(dǎo)致失效時(shí)，簇群的有效節(jié)點(diǎn)數(shù)目會(huì)慢慢降低。新的網(wǎng)絡(luò)無縫覆蓋率ηnew與有效節(jié)點(diǎn)數(shù)S的關(guān)系：

本文提出的分簇路由協(xié)議采用模糊C均值聚類（FCM）算法［5］實(shí)現(xiàn)無線傳感器網(wǎng)絡(luò)中簇的形成。首次完成分簇后，當(dāng)其中某一個(gè)簇群中的所有簇首的能量降低至閾值時(shí)，才開始下一輪分簇。

數(shù)據(jù)匯聚點(diǎn)將WSN中N個(gè)傳感器節(jié)點(diǎn)的坐標(biāo)組成一個(gè)集合X｛Xj，j＝1，2……N｝，該集合中的N個(gè)樣本對應(yīng)于N個(gè)傳感器節(jié)點(diǎn)。設(shè)Vi（i＝1，2……K）為每個(gè)聚類的中心，U（i，j）是第j個(gè)節(jié)點(diǎn)對第i個(gè)簇群的隸屬度函數(shù)。J.C.Bezdek提出的模糊C均值聚類算法（FCM）是一種模糊目標(biāo)函數(shù)法，其目標(biāo)函數(shù)J（U，V）定義為：

其中，U＝［uik］（i＝1，2……C；k＝1，2……N）為隸屬度矩陣，且滿足下式：

其中m的最佳范圍是［1.5，2.5］，dik是第k個(gè)樣本到第i類的距離，定義為：

因此，可以采用新的目標(biāo)函數(shù)使式（5）達(dá)到最小值的必要條件：

這里λj（j＝1，……，n）是式（5）的n個(gè)約束式的拉格朗日乘子。對上式所有的輸入?yún)?shù)進(jìn)行求導(dǎo)運(yùn)算，使式（5）達(dá)到最小的必要條件為：

和

為了防止簇首節(jié)點(diǎn)能量消耗過快導(dǎo)致節(jié)點(diǎn)失效，設(shè)定當(dāng)簇首能量降低至閾值β時(shí)，族首向隊(duì)列中下一個(gè)節(jié)點(diǎn)發(fā)送信息，通知該節(jié)點(diǎn)成為簇首，此簇首則自動(dòng)轉(zhuǎn)換為普通節(jié)點(diǎn)。

在完成分簇后，采用簇首轉(zhuǎn)發(fā)的原理。遠(yuǎn)距離的簇首并不直接同基站進(jìn)行數(shù)據(jù)傳送，而是選擇同其最近的簇首進(jìn)行傳輸，每一個(gè)簇首在接收到其它簇首傳輸?shù)降臄?shù)據(jù)后，進(jìn)行相應(yīng)的數(shù)據(jù)融合處理，然后轉(zhuǎn)發(fā)下一個(gè)簇首，直至數(shù)據(jù)匯集點(diǎn)，此舉極大的縮短了信息的傳送距離，降低了簇首節(jié)點(diǎn)能量消耗。并且本策略中每一個(gè)簇群有多個(gè)節(jié)點(diǎn)輪流當(dāng)選簇首，在仿真實(shí)驗(yàn)中也證實(shí)，此舉保證了簇群穩(wěn)定，在初次確立傳輸路線后，在很長周期內(nèi)可以穩(wěn)定數(shù)據(jù)傳輸路線。

本文提出的路由算法的流程圖如圖2所示。

3 仿真與分析

為了說明算法的效果，我們使用MATLAB對算法進(jìn)行了仿真測試，選擇的仿真場景參數(shù)如表1所示。

比較了最傳統(tǒng)的LEACH算法和本文提出的新算法。圖3為兩種算法的生命周期比較，通過死亡節(jié)點(diǎn)數(shù)隨時(shí)間的變化來判定生命周期的長短，從圖中可以看出新的算法比LEACH算法的生命周期長。

表1 仿真場景參數(shù)

圖2 算法流程圖

圖3 死亡節(jié)點(diǎn)與時(shí)間的關(guān)系

4 結(jié)論

對現(xiàn)有的LEACH路由算法進(jìn)行研究時(shí)發(fā)現(xiàn)，當(dāng)普通節(jié)點(diǎn)當(dāng)選為簇頭節(jié)點(diǎn)后，需要完成數(shù)據(jù)融合、與匯聚節(jié)點(diǎn)通信等任務(wù)，能量消耗較大。但是簇首數(shù)量不固定分簇不均勻，再者，對于反應(yīng)式的無線傳感器網(wǎng)絡(luò)，由于簇首不周期性的發(fā)送監(jiān)測數(shù)據(jù)，從而使得各節(jié)點(diǎn)能量消耗不均勻，LEACH決定節(jié)點(diǎn)的“角色”并沒有考慮節(jié)點(diǎn)的剩余電池能量，存在著負(fù)載均衡策略不完備的缺點(diǎn)［7］。而本文提出的基于FCM的分簇多跳路由算法彌補(bǔ)了LEACH算法的不足，有效地延長了網(wǎng)絡(luò)生存周期。

［1］宋文.無線傳感器網(wǎng)絡(luò)技術(shù)與應(yīng)用［M］.北京：電子工業(yè)出版社，2006.

［2］馬永波.無線傳感器網(wǎng)絡(luò)精確動(dòng)態(tài)定位及其安全性問題研究［D］.吉林大學(xué)2010.

［3］Heinzelman W.B.，Chandrakasan A.P.，Balakrishnan H，An application－specific protocol architecture for wireless microsensor networks，（2009）IEEE Transactions on Mireless Communications，1（4），pp.660－670.

［4］Heinzelman，W.R.；Chandrakasan，A.；Balakrishnan，H."Energy－Efficient Communication Protocol for Wireless Microsensor Networks".In Proceedings of HICSS，00：the 33rd Hawaii International Conference on System Sciences，Wailea Maui，HI，USA，4－7January 2000；Volume 8.

［5］Manjeshwar，A.；Agrawal，D.P."A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks".In Proceedings of the 15th International Parallel and Distributed Processing Symposium IPDPS 2001，San Francisco，CA，USA，23－27April 2001.

［6］紀(jì)金水.基于Zigbee無線傳感器網(wǎng)絡(luò)技術(shù)的系統(tǒng)設(shè)計(jì)［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2007.