基于自組織聚類和蟻群算法的無線傳感器網絡路由算法

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

基于自組織聚類和蟻群算法的無線傳感器網絡路由算法

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

根據無線傳感網絡能量受限的特點，提出一種低能耗路由算法SOC-IACO，算法由自組織聚類算法SOC和改進蟻群算法WAC組成。先通過SOC將節點分簇，選取簇頭構造簇頭數據鏈，再通過WAC構造簇內節點數據鏈。簇內數據沿節點數據鏈匯聚至簇頭、簇頭數據沿簇頭數據鏈匯聚至總簇頭，由總簇頭發送數據至基站。實驗表明，由于聚類過程中考慮了節點分布和簇負載均衡并采用雙層鏈路由，SOC-IACO算法能大幅降低節點能耗提高網絡壽命。

無線傳感器網絡；自組織聚類；蟻群算法

無線傳感器網絡（WSN）的能耗主要來自數據的發送/接收和融合。數據發送的傳輸放大能耗和距離平方成正比。由于WSN中節點通常隨機分布且能量有限，因此減小節點間通信距離，成為降低通信能耗延長網絡壽命的關鍵。目前基于低能耗WSN層次拓撲的主要算法有LECH/LECH-C、HEED、PEGASIS等。

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

PEGASIS[2]單鏈算法則通過構造節點數據鏈，使數據沿鏈傳送至鏈首節點，由鏈首將數據發送至BS。單鏈方案降低了通信距離和能耗，但路由時延大、可靠性差；所采用的貪心算法是局部最優算法，成鏈效果差。

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

SOC-IACO按“輪”進行，每一輪分為初始化和穩定工作兩階段。在輪初始化階段：節點向BS發送狀態信息；BS運行SOC算法，將節點分簇；各簇內依據WAC算法，構造簇節點數據鏈并選取簇頭；構造一條簇頭數據鏈；BS廣播各節點的路由表和工作時隙，初始化結束。在穩定工作階段，各簇內數據沿簇節點數據鏈傳輸至簇頭；類似的，各簇頭數據也沿簇頭數據鏈傳輸至總簇頭；由總簇頭將融合數據發送至BS。

仿真表明SOC-IACO算法降低了節點通信距離、增強了路由穩定性和實時性，大幅提高了網絡壽命。

1 SOC-IACO算法

1.1 算法模型

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

1.2 SOC聚類分簇

針對WSN的特點，我們設計的SOC聚類算法可在指定分簇數量的前提下，優化簇分布、均衡簇負載，為后面使用WAC構造簇節點數據鏈創造條件。SOC算法有如下定義。

定義3聚類。設vm是S中的數據點，則所有類標識符vm_cluste_ID=i的點vm的集合Vci稱為聚類i。聚類非空則為有效聚類；否則為無效聚類。

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

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

以下在2維空間下說明SOC，設100個節點隨機分布在100m×100m的區域S中，指定節點分簇數量為5：

Step1將S劃分成N×N個網格單元Ui；各參考點

如圖1所示。各節點vm尋找最近的參考點uic，令vm_cluster_ID=i，vm∈Vci，節點vm加入聚類i；統計有效聚類數量N_Vc。

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

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

圖1 100個節點隨機分布的網絡拓撲圖

圖2 節點區域的DC聚類效果圖

1.3 WAC簇節點成鏈

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

WAC算法有如下定義和準則。

定義1成鏈路由目標函數：

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

準則1設置一個隨機閾值q∈[0,1]。時刻t，螞蟻k產生一個在[0,1]上均勻分布的隨機變量q0。

若q＜q0，則螞蟻k從節點i轉移到節點j的概率：

為t時刻節點間信息素強度，ηij(t)為節點間距離平方和倒數，α,β為信息素和距離的權重。

若q＞q0，Pij=random,j∈AllowedCity。螞蟻k從AllowedCity中隨機選擇轉移節點j。

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

各個簇內運行WAC算法步驟：

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

1.4 選取簇頭

每一輪將節點分簇、生成簇節點數據鏈后，通過以下方法為各簇選取簇頭。

Step1計算每個節點和BS之間的通信代價：

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

Step2對于所有Vj∈｛Vuc｝和Vcn∈C，計算Vj、Vcn之間的通信代價：

Step3若｛Vuc｝非空，重復Step2，直到所有簇都產生簇頭為止。簇頭數據鏈如下頁圖3所示。

圖3 簇頭節點數據鏈示意圖

綜上所述，在初始化階段，BS通過運行SOC-IACO算法為各節點分配了路由和時隙，接下來的穩定工作階段，網絡通過TDMA方式工作，直到下一輪初始化開始。

2 仿真實驗和分析

使用OMNET++[7]仿真平臺對SOC-IACO和LEACH-C進行對比。設節點隨機分布；節點間通信的數據包大小固定。網絡參數如表1所示，SOC-IACO算法參數如表2所示。表3給出了節點初始能量為0.25J，0.5J，1.0J；隨機分布在100m×100m區域內的仿真結果：

表1 網絡仿真參數設置

表2 SOC-IACO參數設置

表3 不同百分比節點死亡時的輪數

通過以下幾個指標比較LEACH-C和SOC-IACO的性能：

1.FND：第一個節點死亡時間（輪數）。

2.HND：半數節點死亡時間。

3.LND：節點死亡時間，此時可認為網絡失效。

5.EB：能耗均衡性指標

式中Vi(Ere)為節點當前能量；N為節點數量。EB越小節點能耗越均衡，算法性能越好。

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

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

實驗分析：同LEACH-C相比，SOC-IACO算法收斂性好，能大幅提高網絡壽命且節點能耗更均衡。SOC-IACO算法對網絡性能的提高主要來自兩個方面：1.通過考慮節點位置來優化簇分布。2.節點通過雙層鏈路由傳遞數據，降低了通信距離和數據接傳輸能耗。

3 結論

本文提出一種基于自組織聚類和改進蟻群成鏈的低能耗WSN路由算法SOC-IACO。仿真表明SOCIACO降低并均衡了節點能耗，提高了網絡壽命。尤其在節點分布不勻、基站位置較遠的情況下，SOCIACO的表現更優越。

[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].傳感技術學報，2007(11)：62-64.

[4]劉青寶，鄧蘇，張維明.基于相對密度的聚類算法[J].計算機科學，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.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

邱立達（1984-），男，福建福州人，閩江學院物理學與電子信息工程系助教，研究方向：無線傳感器網絡、嵌入式系統研究。

（責任編輯：高堅）

2011-01-01

福建省自然科學基金資助項目（31095010）