无线传感网络中的路由选择及优化研究

李飞，李登

(91497部队，浙江宁波315122)

1 前言

无线传感网络通常是由分布广泛的大量传感器组成的，这些传感器具备动态感知、无线传输通信功能，并且具备一定的计算能力。无线传感器在将感知到的数据通过无线网络传输到处理节点后，就可以组成物联网络，并且具有可扩展、自组织、强稳定性的优势，能够应用到社会领域的各个方面。

我国在无线传感网络方面的研究起步较晚，但是国家对科技领域的重视使得国家自然基金会在21世纪初将无线传感网络列为重点资助项目和重大研究课题，因此国内各大高校、研究机构也纷纷展开了对无线传感网络的研究。

无线传感器的体积极小，因此通常用电池供电，有限的电池容量是无线传感节点长时间使用的最大制约。为了保证无线传感网络的长时间及大规模应用，就需要优化无线网络数据传输时的路由选择，以降低无线传感器的能量消耗，提高能量利用率、延长无线网络寿命。

2 无线传感网络路由协议

无线传感路由协议的目的是实现无线传输网络中数据的转发及路由选择，从而为数据从采集段的无线传感器传输到目的节点寻找一条最优路径。由于无线传感器一般由电池供电，其电量、计算及存储能力的有限性决定了在设计无线传感网络路由协议时需要注意一些问题[1]：

1)能量消耗低且高效。无线传感节点尤其是关键路径上的传感节点的电量耗尽，会导致整个无线传感网络出现传输故障，严重的甚至可能会引起网络瘫痪；无线传感网络间通信时，能耗与传输距离有重要的关联，因此设计无线传感路由时需要权衡节点的能耗，以尽量延长无线传感网络的生命周期。

另外，还要从全局考虑整个无线传感网络的能量均衡，既不能出现“能量消耗热点”，又尽可能避免“能量闲置”，充分提高整个无线传感网络中所有节点的效率。

2)无线传感网络的稳定可靠性。在传感网络中的某个节点出现能量耗尽等问题时，不会影响整个网络的通信，无线传感网络的路由选择需要能够自适应网络结构的拓扑变换。

3)服务质量。路由选择以数据传输为中心，无线路由协议的主要目的是实现传感数据的传输，而无线传感网络结构是会频繁出现变化的，所以并不需要了解数据的采集节点，只需将其传输、转发出去即可。服务质量要求在提供准确、全面的无线传感信息的同时，关注无线传感网络的使用寿命。

根据无线传感网络的拓扑结构，可以将无线传感路由协议分为两大类：平面路由协议及分簇路由协议。在使用平面路由协议的无线传感网络中，每个网络节点的地位和权限是相同的，并不存在管理节点，数据采集及传输是所有节点共同协作完成的，因此平面路由协议的优点是网络结构简单、网络扩展方便。然而，在大规模的无线传感网络中，随着路由跳数的增加，路由选择及数据转发的开销成本也会显著增加。一个典型的平面路由协议网络拓扑如图1所示：

图1 平面路由协议网络拓扑

采用分簇路由协议的无线路由网络中，各个节点的地位有所不同[2]：无线传感网络会以簇为单位进行划分，每个簇中包含一个簇头(cluster head)节点，其余的为普通节点。普通传感节点在采集到数据后会将其传输给簇头节点，簇头节点汇总本簇内所有节点采集到的数据，并将其一起传输到无线传感基站。簇头传感节点的存储、计算能力可以比普通节点的高一些，以完成所有数据的汇总工作。和采用平面路由协议的无线传感网络相比，采用分簇路由协议后，普通网络节点的能量可以得到充分利用，有效延长了无线传感网络的生命周期。分簇路由协议的网络拓扑如图2所示。

图2 分簇路由协议网络拓扑

虽然采用分簇路由协议的无线传感网络比平面路由协议更有优势，但在实际应用中还存在一定的不足[3]：1)组建无线传感网络初期难以确定簇大小。传统的分簇路由协议是将无线传感网络中的所有节点平均分为若干簇，每个簇内的节点数目相同。这种均匀分簇方法可以均衡网络内所有节点的能量负载，但是对于大型无线传感网络中的传感节点随机分布现象并不适用。为此无线传感网络节点组成的集群就不能固定化，而是根据网络内节点分布情况以及能量使用来动态变化。2)簇头选择问题。无线传感网络中的簇头(cluster head)节点会比普通节点存在能多能耗，因此在簇头节点出现问题后，随机选择一个普通节点可能会有继发问题。另外，分簇时仅采用能量指标存在单一性缺陷，需要综合考虑多种指标，并合理分配不同指标的权重。3)局部最优解问题。无线传感网络节点的分布结构可能会导致路由算法陷入局部最优解。

3 分簇算法优化

对于采用分簇路由协议的无线传感网络，其分簇方式、簇大小、簇头选择等问题是限制分簇路由效率及精度的重要因素。

3.1 簇头选择方法

无线传感节点在部署后，每个节点都可以确定自己的物理位置。无线传感基站(Base Station，BS)会周期性地向所有节点广播基站id 和基站的位置信息。无线传感网络内的节点在收到基站的广播信息后，会存储基站id 和基站位置信息，并计算节点到基站的距离Dist，节点距离基站越近，就越有可能成为“能量热点”，同时也具备越强的竞争簇头的能力[4]。

可以使用无线传感网络中的节点剩余能量及到基站的距离Dist两个参数来计算不同节点竞争簇头的优先级，并用模糊映射规则处理簇头竞争的不确定性。

在计算无线传感节点竞争簇头能力，需要使用两个模糊输入变量：节点剩余能量、节点到基站的距离；经过模糊计算后就可以得到无限传感节点的竞争簇头能力。假如某传感节点距离基站最近，并且其剩余的能量还最多，则认为此节点竞争簇头的能力最强，反之亦然。这种簇头选择方法如图3所示。

图3 簇头选择方法

3.2 簇半径计算方法

簇大小的选择会直接影响无线传感网络的寿命，在决定簇大小时需要考虑的因素包括[4]：1)网络中节点的分布密度。如果节点密度较大，则应该减小簇的半径以降低簇头节点的负载，反之则需要适当增加簇半径。2)网络中节点分布的离散程度。无线传感网络中非簇头节点向簇头节点传输数据时的能耗与到簇头节点的距离成正比，因此如果节点分布相对离散，则传输到簇头节点就需要更大的能耗，此时就需要适当减小簇半径，反之则可以适当增加簇半径。3)节点的剩余能量。簇头节点的剩余能量越多，则可以选择越大的簇半径；随着网络使用时间的延长及节点能量的逐渐消耗，可以适当减少簇半径。

考虑到上述因素，在计算簇半径时可以根据无线传感网络中节点的信息来综合权衡。首先，由节点i 自身的地理位置Li计算核函数KH(l-Li)，并和节点到基站的距离Dist、节点的能量一起反映节点的离散程度，以此进行核密度估计。然后，为避免计算全局条件下所有节点的累加值，可以只估计节点i 的K阶近邻，以此降低计算复杂度，得到节点i的局部带宽估计。最后，进行自适应带宽估计。不同节点的邻居节点分布情况是有所不同的，为此基站在发送广播信息时可以向所有节点同时发送一个最小簇半径和最大簇半径参数，每个节点根据邻居节点的分布情况，在最小簇半径和最大簇半径参数之间选择合适的簇半径即可。

4 路由算法优化

4.1 簇间路由算法优化

蚁群算法是一种分布式寻找最优路径的算法，在无线传感网络的路由选择中有广泛应用[5]。算法初期，所有蚂蚁各自选择无规则的路线，并在其访问路径上留下信息素。将蚁群算法应用到无线传感网络的路由选择时，为了确保路由选择算法在开始阶段可以搜索到尽可能多的传输路径，需要对无线传感网络的初始状态路径信息素进行修改。

对于无线传感网络中的所有节点，引入信息素挥发机制：信息素在一次完整访问路径完成后进行更新操作，更新的计算公式为：

其 中ρ是恢复率，(1 -ρ)*τij(t) 是 信息素的挥发过程，Δτij(t)是信息素的增加机制，即路由选择过程中寻找路径时经过某路径所遗留的信息素增量。

信息素在经过若干次的迭代后将得到一个收敛值，根据此收敛值即为簇间初始化信息素浓度最大的值，也就是当前簇选择的下一个簇，这样就实现了簇间的路由选择。

簇间路由选择过程中，经过的每个网络节点需要更新其邻接表，对于多跳路由的无线传感网络，还需要根据簇头节点到基站的距离对簇头节点进行划分，并根据簇头节点的层级更新邻接表：1)只能选择比当前层级低的层级上的簇头，只有低一层级上没有簇头节点时，才扩大簇半径。2)预先设定一个阈值CR，邻接节点的搜索范围固定在CR到2CR之间。

4.2 分簇路由算法优化

在进行簇的划分时，需要根据分簇路由算法选择划分的簇中的节点。

在刚建立簇的初期，已经根据前文介绍的簇半径选择方法和簇头选择方法选择除了簇头，并确定了簇半径。网络内的普通节点收到簇头的广播消息后，就可以知道本簇内已经确定好簇头，因此放弃竞选簇头，并向簇头发送申请加入簇的消息。如果普通节点收到多个簇头发来的广播消息，则选择距其近的节点作为簇头。

随着簇头在一个方向上不断加入普通节点，当距离簇头的距离达到簇半径时，就虚构更改簇内的路由选择方向。此时需要根据举报信息素的累积增量设计转移概率公式，并从邻接表中选择下一方向上的普通节点。这样在一个分簇内进行路由选择时，先在一个方向上不断加入普通节点，方向距离到达簇半径后再改变路由选择方向的方式，可以有效降低无效路由带来的能量损失。路由选择轮数与无效传感网络的平均剩余能量的关系如图4所示。

图4 路由选择优化效果

5 总结

本文对无线传感网络中的路由选择及优化进行研究。首先，本文介绍了无线传感网络的路由协议；接下来本文从簇头选择、簇半径计算等方面对分簇算法进行了优化；最后，本文对簇间及分簇内的路由选择进行了优化。优化结果表明，随着路由选择迭代次数的增加，优化后的无线传感网络平均剩余能量得以有效分布。