邱立达（闽江学院物理学与电子信息工程系，福建福州 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）