基于改进ACO的WSN感知数据传输策略研究

张雅琼，张 慧，郑欢欢

(榆林学院 信息工程学院，陕西 榆林 719000)

0 引 言

无线传感器网络(WSN)是物联网中监测环境与感知数据的重要技术，由大量的长时间持续工作的静态无线节点自治组成。因为无线传感器节点使用电池供电且通常不会更换，所以无线传感器网络的能量消耗和网络生存时间成为研究的热点，而节能路由策略可以显著延长网络生存时间。近年来，有四种不同类型的路由协议不断发展，每种类型下都有大量的路由协议。这些路由协议包括地理路由协议、以数据为中心的路由协议、基于分簇的路由协议和混合路由协议。在这些路由协议中，基于分簇的分层路由协议由于其可扩展性而得到了广泛应用。基于分簇的路由协议将无线传感器节点分成若干组，这些组(即分簇)连接到本地基站(BS)或汇聚(sink)节点。文献[4-7]中提出了大量基于分簇的路由协议，如LEACH、LEACH-C、KLEACH、EEE-LEACH等。其中，LEACH(low-energy adaptive clustering hierarchy)是第一个也是最流行的基于分簇的无线传感器网络分层路由协议。LEACH是一种自组织的自适应分簇协议，利用基于随机性的概率将负载平均分配给网络中的传感器节点。在LEACH协议中，节点能够将自己组织成簇，其中一个节点充当簇头，为其他节点汇聚数据后再将数据发送给sink节点。这使得高能量的节点随机作为簇头，从而节省所有传感器节点的能量(或电池消耗)，进而延长网络生存期。通常LEACH在将数据传输到sink节点之前，在簇头进行数据聚合和数据融合(数据压缩)，通过特定于应用的数据处理，进一步降低能耗，延长网络生存期。

LEACH协议分为两个阶段：

(1)建立阶段，包括簇头选择、簇建立；

(2)稳定阶段，包括数据感知、聚合、压缩和传输。

然而，LEACH在建立阶段是不稳定的，因为它依赖于传感器节点的密度。由于不采用多跳通信，在大型网络中在从远离汇聚节点的簇头节点传输数据时会消耗大量的能量，导致节点过早死亡。影响能量消耗的主要因素有：感知数据、数据处理和无线通信，其中最重要的是无线通信。该文提出了两级分簇，簇内单跳数据传输和簇间多跳传输，大大提高了网络生存期。

1 无线传感器网络模型

1.1 网络假设

无线传感器网络由大量随机分布的无线传感器节点组成。根据节点密度将区域划分为若干个簇，每个簇都有一个簇头，簇内成员节点将数据发给簇头，簇头将数据转发给sink节点，如图1所示。

图1 无线传感器网络模型

网络模型中做出以下假设：

(1)有一个无线传感器节点随机部署并紧密相连的网络；

(2)每个传感器节点具有相同的初始能量与计算能力；

(3)具有不同ID的每个传感器节点将沿着其相邻链路/边缘发送/接收消息；

(4)每个节点知道它自己的坐标值；

(5)网络中的每个节点都知道图中其邻居节点的ID；

(6)每个节点都可以按照网络能耗模型单独发送和接收数据包。

1.2 网络能耗

无线传感器网络的传输采用无线通信系统中的能耗模型，如图2所示。

图2 无线通信能耗模型

发送数据的能耗包括射频模块和信号放大器的能耗，接收节点的能耗仅包括接收电路的能耗。信号放大器的能耗根据收发双方之间的距离

d

可以采用自由空间衰落模型和多路径衰落模型。自由空间衰落模型中，路径损耗指数为2，即

d

能量损耗；多路径衰落模型中，路径损耗指数为4，即

d

能量损耗。参数

ξ

代表数据在自由空间模型传输过程中的损耗，参数

ξ

代表数据在多路径衰落模型传输过程中的损耗。

E

表示发送或接收1比特数据时发送电路或接收电路的能耗。假设无线信道是对称的，即节点1向节点2发送数据的能耗与节点2向节点1发送数据的能耗完全相同。发送

L

比特数据所消耗的能量如式(1)所示：

(1)

其中，

d

表示无线收发节点之间的距离，如式(2)所示：

(2)

(

x

,

y

)与(

x

,

y

)分别表示发送节点

i

与接收节点

j

的坐标值。能耗与所使用的传输放大模型有关，

d

是一个距离常量，如式(3)所示。通常传感器节点到sink的距离大于阈值

d

，而节点之间的距离小于阈值

d

。

(3)

数据传输距离为

d

，接收方接收

L

比特数据消耗的能量如式(4)所示，与传输距离无关。

E

(

M

)=

E

*

L

(4)

1.3 路由策略

基于图论的优化算法已经被用于无线传感器网络的路由。图论方法的主要目标是最小化无线传感器网络(WSN)的总功耗。蚁群优化(ant colony optimization，ACO)可以用于路由建立，即所有簇头节点都试图建立一条到sink节点的最优路径。

在该文提出的策略中，使用ACO算法在簇头和sink节点之间进行最小代价路由，而不是将所有簇头与sink节点并行单跳连接。此外，由于能量最小化是无线传感器网络最关心的问题，使用基于邻近度簇半径划分方法，以便跟踪广播和多跳链路并提供最大地形覆盖的能量优化。

2 改进的路由方案

采用分簇的二级分层网络，该文提出了一种改进的LEACH算法，该算法在最大限度降低网络总能耗的同时，实现了网络流量的最大化。

为了实现目标，汇聚节点向网络中的每个节点广播信标Beacon信号，以得到节点到sink的距离。基于节点密度形成分簇的边界。在LEACH中，簇头是在一段时间后随机选择的。因此，每当随机选择一个新的簇头时，在sink节点处再次形成簇边界。一旦确定了簇边界，在多跳通信模式下，在sink节点上运行蚁群优化算法(ACO)以最小能耗代价确定从簇头到汇聚节点的多跳路径。

无线传感器网络的工作过程如图3所示。

图3 网络运行过程

无线传感器网络开始工作后，sink节点向网络中的所有传感器节点广播消息并接收回信标信号。它基于接收到的信号强度值以及收到的节点坐标值确认与传感器节点的距离。然后，随机竞选簇头并划分簇，在之后的网络运行时，在每个簇中，簇成员节点周期性地在启动阶段生成随机数以用于簇头重新选择，如果生成的该随机值小于随机阈值，则基于簇内节点的可用能量资源来重新选择簇头。簇成员节点通过广播消息通知sink新的簇头。簇头选择后，在sink节点重新划分簇半径。如果生成的随机值大于阈值，则sink节点将等待下一次簇头重选活动。此后，为了节省从簇头到sink节点传输所需的能量，采用ACO来寻找从簇头到sink节点的最佳路径。

2.1 簇头选举与簇的形成

无线传感器网络采用集中式簇间网络拓扑结构。sink节点决定簇头、簇边界以及不同簇之间的路由。下面一一解释。

(1)簇头的选择：一旦传感器节点开始工作，使用公式(5)竞选簇头。

(5)

其中，

p

是期望的簇头占所有节点的百分比，即每个节点成为簇头的概率；

r

是当前运行的轮数；

E

是节点的剩余能量；

E

是节点的初始能量。网络中的所有节点计算上述函数的值，并选择

T

(

n

)最大的节点作为簇头。一旦选择了新的簇头，sink节点就会通过广播消息通知新的簇头集合。(2)计算簇边界：对于给定网络，

d

和

d

分别为最大和最小的节点间距离，簇半径根据每个节点与sink节点之间的距离(SN)计算，使用公式(6)。

(6)

2.2 簇内数据传输

簇头竞选成功以及簇划分结束后，各个簇内传感器节点发送加入消息给簇头，消息中包含自己的剩余能量以及节点ID。簇头节点根据簇内成员节点数量划分时隙，即采用TDMA机制给每个成员分配对应时隙，各个节点在自己的时隙采集并将采集数据发送给簇头节点，在非自己时隙时休眠，以节省能耗。

簇头收到簇成员发送的感知数据后进行数据融合，然后采用簇间多跳路由将信息发送给sink节点。

2.3 基于ACO的簇间路由

蚁群优化(ACO)是一种基于群体的优化技术，以有效地解决组合优化问题。蚁群算法的灵感来自蚁群的食物收集模式，蚂蚁在探访同伴时会留下信息素激素的踪迹来识别目标(食物)。在每一点上，蚂蚁都有两种选择，要么试探性地探索目标，要么利用其他同伴留下的信息素轨迹。在ACO算法中，蚂蚁根据信息素浓度、能量等启发式信息来规划最优路径。将ACO应用到无线传感器网络中是为了利用ACO的自组织性、正反馈性和鲁棒性等，降低路由过程中的能量消耗。在无线传感器网络中引入ACO的原因主要有以下4点：

(1)无线节点能力有限。

无线传感器网络中节点的能量、存储容量和计算能力均有限，在设计路由协议时，需优先考虑路由过程中的能耗与负载均衡问题。将ACO引入到无线传感器网络路由中，根据其算法简单易于实现和群体智能特征可自主地寻找最优路径，节省节点能量，平衡网络负载。

(2)自组织网络。

无线传感器网络的传感器节点通常是随机部署的，节点之间自组织形成网络。ACO中的蚂蚁通过正向反馈原则逐步探索，获取最优路径，在得到最优路径的同时，提高节点能量的利用率。

(3)网络结构的动态性。

无线传感器网络中的节点由于能量耗尽而死亡，以及重新选举簇头等因素使得网络的拓扑结构会经常发生变化，ACO利用其本身的鲁棒性，能够很好地应对这一情况。在网络拓扑发生变化时，蚂蚁采用启发式的路径搜索方式，及时做出调整并再次寻找最优路径，其适应性较好且反应速度较快。

本算法中，在每个簇头点上设置一组概率规则，有助于最小化访问的总成本，并以最佳方式找到通过多个点的最佳路径。假设蚂蚁是一个基于短时记忆的随机路径分配器，在每一步中，为了找到从簇头到sink节点的最小路径，蚂蚁应用随机比例规则来决定下一个访问哪个簇头。当前在簇头

i

的蚂蚁选择去簇头

j

的概率由式(7)给出：

(7)

其中，

γ

是介于0和1之间的常数，

τ

表示信息素轨迹，

η

表示先验可用的启发值，

α

和

β

确定信息素轨迹和启发式信息的相对影响。如果

α

=0，则更可能选择更接近的簇头，这表明存在随机贪婪算法。如果

β

=0，则只放大信息素，不使用启发式方法。两个相邻的簇头

i

和

j

的启发值由式(8)定义：

(8)

τ

(

t

+1)=(1-

v

)*

τ

(

t

)+

δ

*

v

*

τ

(

t

+1,

t

)

(9)

通过反复计算获取从簇头到sink节点的最优路径。

3 算法仿真与性能分析

3.1 仿真环境

对文中算法LEACH-ACO与经典LEACH算法使用MATLAB进行仿真比较并进行性能评估。两个算法都采用了二级路由策略进行数据的传输。仿真参数如表1所示。无线传感器节点随机部署在400 m×400 m的矩形区域。传感器节点在0到10个包之间随机生成数据，每个包的大小为4 kb。为了验证提出的簇间优化方法，实现了一个由200个节点组成的网络，从中选择20个节点作为簇头。

表1 仿真参数

3.2 性能分析

在建立簇后，LEACH-ACO策略利用ACO算法对簇头间的路由进行优化，以解决到sink节点的多跳数据传输。仿真性能评价采用的指标是网络生存期(死亡节点数与轮数的关系)与网络吞吐量(网络生存期内所有节点发送到sink节点的数据包总数)。

(1)网络生存期。

定义当无线传感器网络中有一半的传感器节点死亡时，即认为网络已死亡(在本例中为100)。随着网络运行，系统的总能量将衰减，死亡节点随时间增加，但能量分布是随机的。如图4所示，在LEACH路由算法中，第一个死亡节点在网络运行20轮后便出现，而在LEACH-ACO中第一个死亡节点在大约120轮后出现。在LEACH中，第70轮左右有一半的节点死亡，网络生存期仅为70轮，而在LEACH-ACO中，大约第200轮时网络死亡。因此，提出的LEACH-ACO相比LEACH显著地延长了网络的生存期。

图4 随着网络运行而增加的死亡节点数

(2)网络吞吐量。

以网络生存期内所有无线传感器节点发送给sink节点的数据包总数来衡量网络吞吐量。

如图5所示，因为采用LEACH-ACO算法后无线传感器网络的生存期延长，sink节点收到的数据包总量显著大于采用LEACH算法的无线传感器网络收到的数据包总量，其网络吞吐量是采用LEACH的网络的3倍多。因此，采用LEACH-ACO算法后，sink节点可以收到更多的感知数据，无线传感器网络可以更好地发挥感知作用。

图5 随着网络运行发送给sink节点的数据包总数

4 结束语

随着物联网的发展，作为物联网感知层的无线传感器网络也得到了广泛应用，而无线传感器网络的能耗一直是制约其发展的因素。该文提出了一种应用于无线传感器网络的基于LEACH算法的节能路由，即LEACH-ACO数据传输策略。该方法优先选择剩余能量较高的节点作为簇头，然后sink节点根据无线传感器节点与簇头的距离形成簇边界，一旦选定了簇头并确定了簇的边界即完成了分簇，之后利用ACO算法以最小能耗代价确定从簇头到sink节点的多跳路径。网络采用二级分层结构，簇内基于TDMA进行数据发送，簇间采用多跳路由发送数据到sink节点。仿真结果表明，采用LEACH-ACO算法的无线传感器网络比使用LEACH算法的网络极大地提高了生存时间，同时也大幅提升了网络的吞吐量，sink节点可以获取更多的感知数据。