基于稀疏投影排角分区的无线传感器网络路由协议

贾 琼，乔建华

(太原科技大学 电子信息工程学院，太原 030024)

无线传感器网络(Wireless Sensor Network，WSN)是一种在其检测区域内收集数据信息的通信网络，其主要由通信基站和大量微型传感器构成，能够快速收集自身监测范围内的相关数据，并传送到相应基站中进行处理[1]。因其中的微型传感器体积很小，不能携带很多电池，且更换电池或二次部署十分困难，故其能量有限不可再生，因此如何降低网络能耗并延长网络生命周期成为关键问题。无线传感器网络中大部分能量在通信部分被消耗，其中信号的发送和接收的传输过程中会消耗大部分能量。如果在传感器收集信息时充分利用压缩感知(Compressed Sensing，CS)理论，将能帮助系统减少数据传输量，进而减少能量的消耗量，使得利用率有显著的提升，有利于延长网络的使用寿命。

虽然利用低功耗自适应集簇分层协议(Low Energy Adaptive Clustering Hierarchy，LEACH)[2]时，由于采用了周期轮换机制，簇头的选择只需少量节点，但簇头节点在与汇聚节点通信时是直接的，因此其能量消耗较快[3]。链状传输(Power-Efficient Gathering in Sensor Information System，PEGASIS)[4]协议中，每个节点向距离最近的邻居节点传输信息，数据的传输方式为点对点，节点数据信息最终被传送到汇聚节点，但该协议具有较长的时延从而消耗更多的能量[5]。两种方法各有所长，都将无线传感器网络生命周期延长，但在另一些指标方面都有所降低，例如节点能耗或者时延。本文提出了一种新的基于角度排序分区的无线传感器网络路由协议。该协议通过对监控区域进行划分，使每个区域中的传感器节点与稀疏矩阵中各非零元素相对应进行压缩数据收集，并使用改进精英蚁群算法[6]在每个区域中寻找节一条以汇聚节点为终点且经过该区域全部节点的最短路径，因此其可以减少在传输路径上的能耗。精英蚁群算法相比随机游走算法更能快速直接找到每个分区节点的最优路径，而结合精英蚁群算法的分区投影和随机投影分簇法相比，前者的能量利用率更高，网络使用寿命得到延长。

图1 多跳路由压缩数据收集流程图Fig.1 Schematic diagram of compressive data gathering in a multi-hop routing

1 分区原理及精英蚁群算法

1.1 压缩感知基本理论

根据压缩感知[7-8]理论在采集可压缩信号或者稀疏信号时，不必使用通常的高频率采样，其采样频率可以远低于Nyquist频率，只需在后期利用非线性重建算法便能将所采集的信号完美恢复[9]。设x为N维稀疏信号，利用N×N维稀疏变换矩阵Ψ可将x分解为:

x=Ψθ

(1)

其中：θ是K阶稀疏的N×1维列向量，也就是说θ中非零项有K个，且满足K≪N.假设M×N维度的投影矩阵(或观测矩阵、测量矩阵)Φ，通过对稀疏信号在测量矩阵Φ下进行投影，即可获得M个观测值y，且有M≪N，即:

y=Φx=ΦΨθ=Tθ

(2)

因此：T命名为传感矩阵；y称之为M×1维的列向量，为测量值。

由压缩感知理论可得，如果传感矩阵T符合有限等距性质(Restricted Isometry Property，RIP)，那么式(2)存在确定解。假设存在δ∈(0，1)使所有K阶稀疏信号θ满足下式:

(3)

(4)

1.2 分区原理

通过压缩感知理论可得，若测量矩阵Φ为M×N维的矩阵，x是N×1维的列向量，可得：

(5)

(6)

通过式(5)可以得出，针对N个节点xj(j=1，2，…N)，可将Φ中每行元素与x进行一系列乘加运算，最终获得M个测量结果。由于测量矩阵Φ为稀疏矩阵，即Φ的每行会出现很多0元素，将Φ的每行作为无线传感器网络每条路径的投影，可将Φ分为M块，每块为1×N的矩阵，且每块包含0元素但不全为0，如下：

Φ=

(7)

因每个块矩阵中包含很多0元素，故每个块矩阵与x相乘，只需要将块矩阵中的非零元素与x中对应的数据相乘再传输，可大大减少数据的传输量，节省网络能消。而每个块矩阵对应分区后的每条路径，路径将数据传输到Sink 节点，M条路径中所有信息相加后得到最终测量值。上述传感矩阵可结合测量值来重构信号数据。如果只需要其中一部分数据，那么在重构时只需取其中某些块即可。测量矩阵是随机的，所以部分随机矩阵依旧满足 RIP，重构信号时仍可用。

1.3 精英蚁群算法

蚁群算法(Ant Clony Optimization，ACO)[10]是由意大利学者Dorigo M等人于1991年首先提出并首先使用在解决旅行商问题(Traveling Saleman Problem，TSP)上。蚁群算法的基本原理来源于自然界蚂蚁觅食的最短路径原理：蚂蚁在寻找食物源时，能在其走过的路径上释放一种蚂蚁特有的分泌物即信息素，使得一定范围内的其他蚂蚁能够察觉到其分泌的信息素并由此信息素浓度影响他们以后的行为。当一些路径上通过的蚂蚁越来越多时，其留下的信息素也越来越多，以致信息素浓度增大，所以蚂蚁选择选该路径的概率也越高，从而更增加了该路径的信息素强度。蚁群算法如图2所示。

图2 蚁群算法示意图Fig.2 Schematic diagram of the ant colony algorithm

精英蚁群算法是对蚁群算法的改进，其精英策略(Elitist Strategy)的基本思想是：在每次循环结束后对所有已经发现的最优解给予额外的信息素增强，即强化找到优于当前最优路径的蚂蚁对信息素浓度的影响，同时消减找到差于当前最优路径的蚂蚁对信息素浓度的影响，其目的是为了使到目前为止所找出的最优解在下一次循环中对蚂蚁更具有吸引力[11]。引入精英策略以后，收敛速度明显加快，但是复杂度并没有增加，仍然等同于经典蚁群算法。

2 基于位置的排角分区方法

2.1 分区

本文提出一种角度排序分区法，其建立在节点的空间位置基础上，适用于感器节点随机分布网络。为均匀分布投影节点，在划分监测区域时，每个被划分的区中节点个数相等。所有节点均为投影节点，与收集到的数据进行加权处理，然后依次传给下一节点，直到传送到Sink节点。具体的实施过程如下：

1)确定分区数。

2)根据每个节点与Sink节点之间连线与横轴的角度，依次将各角度按照从小到大的方式进行排序。

3)根据分区数确定每个区域内的节点个数，并根据各节点的角度找到对应节点。

4)在每个区域寻找传输该区所有节点数据的最优路径。

5)将数据投影到节点上，依次进行乘加，并送至Sink节点，然后利用上述重构算法来恢复原始信号数据。

6)回到步骤(1)，开始新的投影重构。

2.2 分区数目的确定

图 3 所示为本文在计算过程所采用的网络信道模型[12]。

图3 网络信道模型Fig．3 Network channel model

假设在C×C正方形区域内随机分布着N个传感器节点，并且所有节点在初始时刻能量储备是相同的。将正方形区域划分为M个子区域，使每个区域内节点数相同，则每个区域中包含N/M个节点。假设每个节点每跳的传输距离为d，造成能量消耗的因素主要有三方面：对上一节点成员信息进行接收、融合接收到的数据、将融合之后的数据传递到下一个节点。

2.2.1 能量模型

本文将采用文献[13]中的二次衰落模型对节点所造成的能量消耗进行阐述，每个节点在传输信号时，其所消耗的能量与信号传输距离之间的关系如式(8)所示。

Etransmit=kEelect+kEfsd2

(8)

其中：k表示被传输数据的信息位，单位为bit；d表示节点间距离；Eelect为在发射电路或接收电路中处理单位数据所消耗的能量；Efs表示耗散能量，其受传输信号的模型会影响。

此时每个节点在接收数据时，其消耗的能量由式(9)计算。

Erecieve=kEelect

(9)

此时每个节点在融合数据时，其消耗的能量由式(10)计算。

Efusion=kEDA

(10)

式中：EDA为数据融合的能量消耗。

假设数据从某一个节点发送到Sink节点时，其经过了x个节点，那么信号整个传输过程消耗的能量计算过程如式(11)所示。

Enode-x=(x+1)Etransmit(k，di)(i=1，2，…x+1)+

xErecieve+xEfusion=(x+1)kEelect+

(11)

由式(11)可知，如果数据长度k不变，那么数据传输过程中主要在发送信号、接受信号以及最终的融合处理这三部分消耗能量，而影响能量消耗的因素有两部分：

1)由经过的节点数x决定的对数据进行处理的能量消耗(2x+1)kEelect；

2.2.2 分区数目的确定

一条路径有N/M个节点，假设路径中两两节点间距离均值为d，则一条路径的能量消耗如式(12)所示。

(12)

M个区域中M条路径的总能耗如式(13)所示。

(13)

对Etotal求导，得到最优分区数为：

(14)

3 仿真

用 Matlab 作为仿真工具，在寻找每个区域的路径时用蚁群算法和随机游走算法进行对比，并且用新路由协议与LEACH协议进行性能比较，从死亡节点数量对比得出协议性能。表1给出本次仿真的主要参数。

表1 仿真数据(场景1、场景2)Tab.1 Simulation data (scenario 1，scenario 2)

3.1 仿真研究

在进行仿真时，针对无线传感器器网络以及节点所提出的假设如下：

1)在系统所监测的区域中，传感器节点的分布均随即且均匀。

2)传感器节点都是静止的。

3)Sink节点位置固定在区域某一处。

4)Sink节点存储和计算能力较强，其能量和存储容量不受限。

5)节点自己无法测量到自身位置信息。

6)节点具有相同而通信能力。

7)每个节点能量受限且在融合单位数据上对能量的消耗是相同的。

8)在检测范围内根据单位面积所检测的数据量相同。

3.2 仿真分析

仿真过程中，参数设置如参数表。正方形区域为100×100，其中节点总数N为100个，共划分为M≈8.47区域，由于分区数需为整数，设计的稀疏投影矩阵每行中非零元素的个数相同，且每个区节点个数相同且节点个数不宜太少，故在此取M=5，则每个区的节点个数N/M=20.

将检测区域内的节点按照上述方法计算得到分区数后进行分区如下。图4(a)是分区后，每个区由随机游走算法找到的5条路径。图4(b)是分割区域后由精英蚁群算法找到的每个区的路径。

图4 各区域的路径图Fig.4 Road map of each area

从路径图以及路径长度对表均可以看出，通过随机游走寻找到的路径并不能有效减少数据传输的路径，故其能量消耗也不能有效减少，而通过精英蚁群算法找到的路径相对比随机游走找的的路径要更为简短，更能减少数据传输中的能耗。

表2 路径长度对比表Tab.2 Path length comparison table

图5即根据均匀分区的投影以及随机分簇投影两种方法针对节点死亡数所进行的对比图。

通过图5可知，在网络运行的初期，死亡节点出现在均匀分区的时间就比基于随机分簇投影出现死亡节点的时间晚，在网络的继续运行中，基于均匀分区的死亡节点数都比基于随机分簇的死亡节点数少，但随着网路的运行，二者之间的差距越来越小，在运行300轮之后，二者的死亡节点数均达到90%，可认为网络基本瘫痪。

图5 基于均匀分区和随机分簇投影的WSN死亡节点数比较Fig.5 Comparison of WSN dead nodes based on uniform partitioning and random clustering projection

假设正方形区域为200×200，其中共有400个节点，M≈16.94，并取M≈16，则每个区的节点个数N/M=25.图6为其由蚁群算法找到的最优路径图。

图6 200×200区域内蚁群算法找到的最优路径图Fig.6 Optimal path map found by ant colony algorithm in 200×200 area

图7为在该场景下两种算法的节点死亡情况对比图。

图7 200×200区域基于均匀分区和随机分簇投影的WSN死亡节点数比较Fig.7 Comparison of WSN dead nodes based on uniform partitioning and random clustering projection in 200×200 region

由图7可以看出，在200×200区域内，随着网路运行到90轮附近，二种方式的死亡节点数几乎一致，在运行到160轮之时，分簇的死亡节点数开始比分区少，说明此时分区不再具有优势。

3.3 均匀投影的压缩数据收集

压缩数据收集主要步骤如下:

1)根据网络参数，确定划分区域的数量，并以此划分监测区域。

2)在每个区域内利用蚁群算法找到经过所有节点的最优路径。

3)根据CS理论计算节点数据和稀疏矩阵加权值，并通过一跳或多跳方式送到Sink节点。

4)经过M次传输，Sink 节点将所有获得数据相加，由此得到M个测量值。然后将测量值代入算法，可以重构得到原始信号数据。

4 结语

提出了一种压缩数据收集方法，其建立在排角分区投影基础上，能够解决随投影节点机带来的问题，同时降低能耗。该方法中每个区域节点数量相同，确保了每个区域投影节点分布均匀。最后通过仿真分析，发现该方法比分簇方法在能量消耗和网络运行等方面更具优势，延长了网络使用寿命。未来工作将进一步完善所提出的路径协议，并考虑考相邻区域内的边界点节点位置，有可能部分节点与所属区域内节点的距离较远但却距相邻区域内边界节点较近，那么该节点即所需重新考虑分区的存在争议的边界节点，对存在争议的邻居节点考虑具体该如何重新分区问题做进行进一步研究。