基于自組織聚類和蟻群算法的無線傳感器網(wǎng)絡(luò)路由算法

邱立達(dá)（閩江學(xué)院物理學(xué)與電子信息工程系，福建福州 350108）

基于自組織聚類和蟻群算法的無線傳感器網(wǎng)絡(luò)路由算法

邱立達(dá)（閩江學(xué)院物理學(xué)與電子信息工程系，福建福州 350108）

根據(jù)無線傳感網(wǎng)絡(luò)能量受限的特點(diǎn)，提出一種低能耗路由算法SOC-IACO，算法由自組織聚類算法SOC和改進(jìn)蟻群算法WAC組成。先通過SOC將節(jié)點(diǎn)分簇，選取簇頭構(gòu)造簇頭數(shù)據(jù)鏈，再通過WAC構(gòu)造簇內(nèi)節(jié)點(diǎn)數(shù)據(jù)鏈。簇內(nèi)數(shù)據(jù)沿節(jié)點(diǎn)數(shù)據(jù)鏈匯聚至簇頭、簇頭數(shù)據(jù)沿簇頭數(shù)據(jù)鏈匯聚至總簇頭，由總簇頭發(fā)送數(shù)據(jù)至基站。實(shí)驗(yàn)表明，由于聚類過程中考慮了節(jié)點(diǎn)分布和簇負(fù)載均衡并采用雙層鏈路由，SOC-IACO算法能大幅降低節(jié)點(diǎn)能耗提高網(wǎng)絡(luò)壽命。

無線傳感器網(wǎng)絡(luò)；自組織聚類；蟻群算法

無線傳感器網(wǎng)絡(luò)（WSN）的能耗主要來自數(shù)據(jù)的發(fā)送/接收和融合。數(shù)據(jù)發(fā)送的傳輸放大能耗和距離平方成正比。由于WSN中節(jié)點(diǎn)通常隨機(jī)分布且能量有限，因此減小節(jié)點(diǎn)間通信距離，成為降低通信能耗延長(zhǎng)網(wǎng)絡(luò)壽命的關(guān)鍵。目前基于低能耗WSN層次拓?fù)涞闹饕惴ㄓ蠰ECH/LECH-C、HEED、PEGASIS等。

其中LECH-C[1]是經(jīng)典分簇算法。該協(xié)議采用先選取簇頭，再分簇的方法。每一輪中，由于簇頭不同，形成的簇分布也不同。由于沒有考慮節(jié)點(diǎn)位置信息，常導(dǎo)致分簇不均勻。且其簇內(nèi)采用“星型”通信方式使得節(jié)點(diǎn)能耗很大。

PEGASIS[2]單鏈算法則通過構(gòu)造節(jié)點(diǎn)數(shù)據(jù)鏈，使數(shù)據(jù)沿鏈傳送至鏈?zhǔn)坠?jié)點(diǎn)，由鏈?zhǔn)讓?shù)據(jù)發(fā)送至BS。單鏈方案降低了通信距離和能耗，但路由時(shí)延大、可靠性差；所采用的貪心算法是局部最優(yōu)算法，成鏈效果差。

針對(duì)LECH-C和PEGASIS的缺點(diǎn)，本文提出了一種分簇成鏈路由算法SOC-IACO。SOC-IACO由自組織聚類算法SOC和改進(jìn)蟻群算法[3]WAC組成，其中SOC是我們針對(duì)WSN設(shè)計(jì)的聚類算法，[4]充分考慮了節(jié)點(diǎn)分布和簇均衡負(fù)載；而WAC是在基本蟻群算法[5]的基礎(chǔ)上通過使用新的信息素更新公式、領(lǐng)域交換等措施來擴(kuò)大解空間和提高收斂速度。

SOC-IACO按“輪”進(jìn)行，每一輪分為初始化和穩(wěn)定工作兩階段。在輪初始化階段：節(jié)點(diǎn)向BS發(fā)送狀態(tài)信息；BS運(yùn)行SOC算法，將節(jié)點(diǎn)分簇；各簇內(nèi)依據(jù)WAC算法，構(gòu)造簇節(jié)點(diǎn)數(shù)據(jù)鏈并選取簇頭；構(gòu)造一條簇頭數(shù)據(jù)鏈；BS廣播各節(jié)點(diǎn)的路由表和工作時(shí)隙，初始化結(jié)束。在穩(wěn)定工作階段，各簇內(nèi)數(shù)據(jù)沿簇節(jié)點(diǎn)數(shù)據(jù)鏈傳輸至簇頭；類似的，各簇頭數(shù)據(jù)也沿簇頭數(shù)據(jù)鏈傳輸至總簇頭；由總簇頭將融合數(shù)據(jù)發(fā)送至BS。

仿真表明SOC-IACO算法降低了節(jié)點(diǎn)通信距離、增強(qiáng)了路由穩(wěn)定性和實(shí)時(shí)性，大幅提高了網(wǎng)絡(luò)壽命。

1 SOC-IACO算法

1.1 算法模型

為便于比較，本文采用和LECH-C算法相同的網(wǎng)絡(luò)模型：1.各節(jié)點(diǎn)位置已知并可相互通信，使用第一類無線通信能耗模型。[6]2.BS能夠根據(jù)接收到的節(jié)點(diǎn)信息運(yùn)行相關(guān)算法，為網(wǎng)絡(luò)分配路由。

1.2 SOC聚類分簇

針對(duì)WSN的特點(diǎn)，我們?cè)O(shè)計(jì)的SOC聚類算法可在指定分簇?cái)?shù)量的前提下，優(yōu)化簇分布、均衡簇負(fù)載，為后面使用WAC構(gòu)造簇節(jié)點(diǎn)數(shù)據(jù)鏈創(chuàng)造條件。SOC算法有如下定義。

定義3聚類。設(shè)vm是S中的數(shù)據(jù)點(diǎn)，則所有類標(biāo)識(shí)符vm_cluste_ID=i的點(diǎn)vm的集合Vci稱為聚類i。聚類非空則為有效聚類；否則為無效聚類。

定義4聚類離散度。有效聚類i的聚類離散度：

式中d(vm,uic)為該聚類中的數(shù)據(jù)點(diǎn)Vm到參考點(diǎn)uic的距離。num(Vci)為該聚類的數(shù)據(jù)點(diǎn)數(shù)量。

以下在2維空間下說明SOC，設(shè)100個(gè)節(jié)點(diǎn)隨機(jī)分布在100m×100m的區(qū)域S中，指定節(jié)點(diǎn)分簇?cái)?shù)量為5：

Step1將S劃分成N×N個(gè)網(wǎng)格單元Ui；各參考點(diǎn)

如圖1所示。各節(jié)點(diǎn)vm尋找最近的參考點(diǎn)uic，令vm_cluster_ID=i，vm∈Vci，節(jié)點(diǎn)vm加入聚類i；統(tǒng)計(jì)有效聚類數(shù)量N_Vc。

Step4重復(fù)Step3，直到num(Vci)=0，將聚類Vci標(biāo)記為空聚類，N_Vc減1。

Step5重復(fù)Step2，直到有效聚類數(shù)量N_Vc=5為止。分簇效果如圖2所示。

圖1 100個(gè)節(jié)點(diǎn)隨機(jī)分布的網(wǎng)絡(luò)拓?fù)鋱D

圖2 節(jié)點(diǎn)區(qū)域的DC聚類效果圖

1.3 WAC簇節(jié)點(diǎn)成鏈

節(jié)點(diǎn)分簇后，在各簇內(nèi)利用WAC算法構(gòu)造簇節(jié)點(diǎn)數(shù)據(jù)鏈。根據(jù)能耗模型，我們希望得到的數(shù)據(jù)鏈中鄰近節(jié)點(diǎn)的距離平方和最小。WAC通過改變螞蟻分布方式，使用新的信息素更新公式，使用2-opt調(diào)整解結(jié)果等措施，擴(kuò)大了解空間并提高了收斂速度。

WAC算法有如下定義和準(zhǔn)則。

定義1成鏈路由目標(biāo)函數(shù)：

式中X為一個(gè)路徑解，算法的目的就是求解L(X)的最小值L(X*)，X*為所求最優(yōu)路徑。

準(zhǔn)則1設(shè)置一個(gè)隨機(jī)閾值q∈[0,1]。時(shí)刻t，螞蟻k產(chǎn)生一個(gè)在[0,1]上均勻分布的隨機(jī)變量q0。

若q＜q0，則螞蟻k從節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的概率：

為t時(shí)刻節(jié)點(diǎn)間信息素強(qiáng)度，ηij(t)為節(jié)點(diǎn)間距離平方和倒數(shù)，α,β為信息素和距離的權(quán)重。

若q＞q0，Pij=random,j∈AllowedCity。螞蟻k從AllowedCity中隨機(jī)選擇轉(zhuǎn)移節(jié)點(diǎn)j。

準(zhǔn)則2螞蟻k完成一次旅行后，按式（5）更新路徑信息素：

各個(gè)簇內(nèi)運(yùn)行WAC算法步驟：

Step3若未達(dá)到迭代次數(shù)，初始化Tabu和AllowedCity，重復(fù)Step2；否則輸出最優(yōu)路徑解L(X)。

1.4 選取簇頭

每一輪將節(jié)點(diǎn)分簇、生成簇節(jié)點(diǎn)數(shù)據(jù)鏈后，通過以下方法為各簇選取簇頭。

Step1計(jì)算每個(gè)節(jié)點(diǎn)和BS之間的通信代價(jià)：

式中，Ei為節(jié)點(diǎn)i剩余能量，ETx(k,di-BS)為節(jié)點(diǎn)i與BS通信能耗。選擇cost(i,BS)最小的節(jié)點(diǎn)va作為其

Step2對(duì)于所有Vj∈｛Vuc｝和Vcn∈C，計(jì)算Vj、Vcn之間的通信代價(jià)：

Step3若｛Vuc｝非空，重復(fù)Step2，直到所有簇都產(chǎn)生簇頭為止。簇頭數(shù)據(jù)鏈如下頁(yè)圖3所示。

圖3 簇頭節(jié)點(diǎn)數(shù)據(jù)鏈?zhǔn)疽鈭D

綜上所述，在初始化階段，BS通過運(yùn)行SOC-IACO算法為各節(jié)點(diǎn)分配了路由和時(shí)隙，接下來的穩(wěn)定工作階段，網(wǎng)絡(luò)通過TDMA方式工作，直到下一輪初始化開始。

2 仿真實(shí)驗(yàn)和分析

使用OMNET++[7]仿真平臺(tái)對(duì)SOC-IACO和LEACH-C進(jìn)行對(duì)比。設(shè)節(jié)點(diǎn)隨機(jī)分布；節(jié)點(diǎn)間通信的數(shù)據(jù)包大小固定。網(wǎng)絡(luò)參數(shù)如表1所示，SOC-IACO算法參數(shù)如表2所示。表3給出了節(jié)點(diǎn)初始能量為0.25J，0.5J，1.0J；隨機(jī)分布在100m×100m區(qū)域內(nèi)的仿真結(jié)果：

表1 網(wǎng)絡(luò)仿真參數(shù)設(shè)置

表2 SOC-IACO參數(shù)設(shè)置

表3 不同百分比節(jié)點(diǎn)死亡時(shí)的輪數(shù)

通過以下幾個(gè)指標(biāo)比較LEACH-C和SOC-IACO的性能：

1.FND：第一個(gè)節(jié)點(diǎn)死亡時(shí)間（輪數(shù)）。

2.HND：半數(shù)節(jié)點(diǎn)死亡時(shí)間。

3.LND：節(jié)點(diǎn)死亡時(shí)間，此時(shí)可認(rèn)為網(wǎng)絡(luò)失效。

5.EB：能耗均衡性指標(biāo)

式中Vi(Ere)為節(jié)點(diǎn)當(dāng)前能量；N為節(jié)點(diǎn)數(shù)量。EB越小節(jié)點(diǎn)能耗越均衡，算法性能越好。

如上頁(yè)表3所示(以節(jié)點(diǎn)初始能量0.5J為例)，相較于LEACH-C：當(dāng)網(wǎng)絡(luò)規(guī)模為100m×100m時(shí)，SOCIACO將FND，HND和LND分別提高了161%、55.8%和70.6%；CONV從0.012提高至0.365，提高了18.7倍；第一個(gè)節(jié)點(diǎn)死亡時(shí)，各輪能耗均衡性比較如圖4所示。

圖4 LEACH-C和SOC-IACO能量均衡性比較(節(jié)點(diǎn)初始能量0.5J)

實(shí)驗(yàn)分析：同LEACH-C相比，SOC-IACO算法收斂性好，能大幅提高網(wǎng)絡(luò)壽命且節(jié)點(diǎn)能耗更均衡。SOC-IACO算法對(duì)網(wǎng)絡(luò)性能的提高主要來自兩個(gè)方面：1.通過考慮節(jié)點(diǎn)位置來優(yōu)化簇分布。2.節(jié)點(diǎn)通過雙層鏈路由傳遞數(shù)據(jù)，降低了通信距離和數(shù)據(jù)接傳輸能耗。

3 結(jié)論

本文提出一種基于自組織聚類和改進(jìn)蟻群成鏈的低能耗WSN路由算法SOC-IACO。仿真表明SOCIACO降低并均衡了節(jié)點(diǎn)能耗，提高了網(wǎng)絡(luò)壽命。尤其在節(jié)點(diǎn)分布不勻、基站位置較遠(yuǎn)的情況下，SOCIACO的表現(xiàn)更優(yōu)越。

[1]W.B.Heinzelman，A.P.Chandrakasan，H.Balakrishnan.An Application-Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Transactions on Wireless Communication，2002(4):660.

[2]S.Lindesy，C.S.Raghavendra.PEGASIS:Power-Efficient Gathering in Sensor Information System[C].IEEE Aerospace Conference，2002:1-8.

[3]馮躍喜，金心宇.基于改進(jìn)型蟻群算法的無線傳感路由協(xié)議[J].傳感技術(shù)學(xué)報(bào)，2007(11)：62-64.

[4]劉青寶，鄧蘇，張維明.基于相對(duì)密度的聚類算法[J].計(jì)算機(jī)科學(xué)，2007(2)：92-44.

[5]W.J.Gutjahr.ACO algorithms with guaranteed convergence to the optimal solution[J].Information Processing Letters，2002(82):145-153.

[6]W.B.Heinzelman，A.P.Chandrakasan，H.Balakrishnan.Energy Efficient Communiction Protocol for Wireless Microsensor Networks [C].the 33rd Annual Hawaii international Conference on System Science.2000(8):3005-3014.

[7]Wang，K.Liu，F(xiàn).Hu.Simulation of wireless sensor networks localization with omnet[C].In Mobile Technology，Applications and Systems，2005 2nd International Conference on Mobile Technoloy，Applications and Systems，2005.

A Wireless Sensor Networks Routing Protocol Based on Self-organizing Clustering and Intelligent Ant Colony Algorithm

Qiu Lida
(DepartmentofPhysicsandEletronicInformationEngineeringofMinjiangUniversity,Fuzhou350108,China)

Based on the feature of energy deficiency in wireless sensor networks,This paper proposes a centralized clusterchain power efficient routing algorithm SOC-IACO,which consists of self-organizing clustering algorithm(SOC)and intelligent Ant Colony Algorithm(IACO).BS firstly uses SOC algorithm to form clusters and selects associated cluster heads and a cluster-heads chain will be constructed;then BS uses IACO algorithm to construct a near-optimal nodes chain for each cluster.Data will be aggregated and transmitted along cluster nodes chain to cluster head.Then aggregated data of every head will be transmitted along cluster-heads chain to BS.Simulation results show that SOC-IACO reduces the node energy consumption and extend the network lifetime by considering nodes distribution in clustering process and using double-layer chain structure to transmit data.

wireless sensor networks,self-organizing clustering algorithm,ant colony algorithm.

TN91

A

1673-8535（2010）06-0030-06

邱立達(dá)（1984-），男，福建福州人，閩江學(xué)院物理學(xué)與電子信息工程系助教，研究方向：無線傳感器網(wǎng)絡(luò)、嵌入式系統(tǒng)研究。

（責(zé)任編輯：高堅(jiān)）

2011-01-01

福建省自然科學(xué)基金資助項(xiàng)目（31095010）