无线传感网中基于均方差赋权法的路由协议∗

孙佳美，任秀丽

(辽宁大学信息学院，沈阳110036)

无线传感器网络WSN(Wireless Sensor Network)是由大量多功能、低功耗、廉价的传感器节点和一个Sink节点或基站组成的网络系统，节点间采用自组织无线通信的方式建立连接并传递信息，协同完成特定功能[1]。传感器节点的能量、计算能力、存储容量和通信带宽等资源极为有限，如何设置有效的能量均衡策略，控制节点的能量消耗成为无线传感器网络路由协议研究的重点。

针对低功耗的无线网络，IETF工作组制定了RPL路由协议[2]。在RPL路由协议中，根据路由度量计算节点rank值，通过比较节点rank值选择下一跳。节点根据网络状况动态调整数据包发送频率，减少了节点能耗。但采用跳数作为路由度量，与节点间实际距离存在偏差。而且跳数少的路径其单跳距离可能较长，影响链路质量。

关于RPL路由协议的优化研究中，文献[3](ELT-RPL)提出了一种期望寿命路由度量，用于估算网络中瓶颈节点的生存时间，以此构建网络拓扑；并依据最大最小原则选择父节点，延长了网络的生命周期。但该协议增加了控制包的数量造成包碰撞率增加，导致收包率下降。文献[4](OBL-RPL)通过对节点的剩余能量进行分级和调节节点的通信半径的方法，对目标函数进行改进。该协议均衡了节点的负载，但会增加路径跳数，并且存在网络抖动现象。文献[5](EAM-RPL)将链路质量与节点能耗相结合，提出了能量感知路由度量。该路由协议延长了网络的生命周期。但在网络后期，由于父节点状态信息更新不及时，导致节点做出错误的路由选择，加速瓶颈节点的死亡。文献[6](HE-CRPL)提出一种高效的基于簇父集协作通信的路由协议，该协议在选择簇父节点时综合考虑节点的通信可靠性与节点的剩余能量，并引入期望寿命ELT进行最优簇父集选择。虽然延长了网络的生命周期，但增加了簇父节点之间的通信量。文献[7](HIT-RPL)提出一种基于机会路由的RPL路由协议。节点采用任播的方式传输数据包，数据包的传输不依赖某一固定链路。虽然提高了网络的可靠性，但目的节点会接收到多个来自不同路径的相同数据包，增加了目的节点和中继节点的负载。文献[8](EB-RPL)提出一种带有电量估算的路由协议，设计了一种基于能量消耗速率的父节点电量估算策略，通过估算父节点电量进行路由决策。延长了网络的生命周期，但节点的预测误差会影响节点的路由决策。以上这些算法在处理多指标优化问题上，采用加权法将多个链路质量指标组合成一个指标，各指标的权重系数都是根据主观经验值给定。由于网络环境复杂多变，链路质量指标在网络运行过程中不断发生变化，采用固定的主观权重无法根据实际指标的变化作出自适应的调整，路由决策难以满足网络的实际需求。

通过分析以上协议，本文提出了一种无线传感网中基于均方差赋权法的路由协议MSDRP(Mean-Squared Deviation weight decision Routing Protocol)。构造一种新的节点距离路由度量。提出了一个节点邻域空间划分模型，并在节点邻域内确定一个参考点。根据余弦定理将节点距邻节点距离，节点距Sink节点距离，邻节点距Sink节点距离，节点的通信半径等多个变量的取值及其变化关系转化到节点邻域内参考点距邻节点距离这一个变量的测量上。提高邻节点距离这一评价指标所考虑因素的全面性和合理性。综合考虑邻节点的剩余能量，邻节点的距离，邻节点的链路质量和邻节点的负载这四个评价指标，根据均方差赋权法对节点评价指标的权值进行动态调整。通过目标函数公式计算出邻节点的目标函数值，选择目标函数值最大的节点作为下一跳，建立数据传输路径。仿真结果表明该路由协议能够有效均衡节点能耗，延长网络的生命周期。

1 系统模型

1.1 网络与能耗模型

网络中传感器节点随机分布在监测区域内，且部署后位置固定。另外，节点之间的距离采用文献[9]中的RSSI测距方法计算。传感器节点依靠电池供电，能量有限。节点ID编号唯一，初始通信半径都相同。Sink节点位置固定，能量充足。所有节点可以接收来自Sink节点广播的数据包。节点发送和接收数据所消耗的能量采用与文献[10]中相同的能耗模型进行计算。

图1 节点的邻域划分

1.2 节点邻域划分模型

节点的单跳通信范围是节点的邻域。节点邻域模型将节点邻域划分成两部分，如图1所示。点A表示Sink节点，点Nx表示传感器节点。节点Nx的邻域用圆Nx来表示，圆Nx的半径为传感器节点的初始通信半径R0。Sink节点的通信区域用圆A表示，圆A的半径为节点 Nx距 Sink节点的距离 d(Nx，Sink)。将圆Nx与圆A的相交区域视为节点Nx的前向邻域(如图1中的阴影区域)，圆Nx内的剩余区域为节点Nx的后向邻域。称节点Nx前向邻域内的邻节点为节点Nx的前向邻节点。

1.3 节点邻域内的参考点

根据节点Nx的邻域划分模型确定节点Nx邻域内的参考点，如图2所示。过点A(Sink节点)和点Nx作一条直线Lx。直线Lx与圆Nx相交于圆A内一点Ox，将点Ox作为节点Nx邻域内的参考点。两圆的交点B和C分别是节点Nx邻域内的两个临界点。

图2 节点邻域内的参考点

如图2所示，设节点Nk是节点Nx的前向邻节点。则节点Nk距Sink节点的距离为d(Nk，Sink)，节点Nk距节点Nx的距离为d(Nk，Nx)。节点Nk距节点Nx邻域内参考点Ox的距离为d(Nk，Ox)。节点Nx距Sink节点的距离为d(Nx，Sink)，节点Nx距其邻域内的参考点Ox的距离为d(Nx，Ox)＝R0，R0为节点的初始通信半径。设三角形 ΔNkNxA中∠NkNxA的度数为θxk。根据余弦定理，角θxk的余弦值cosθxk可以分别用式(1)和式(2)来表示。

联合式(1)和式(2)可以推导出节点Nk距参考点 Ox的距离 d(Nk，Ox)，如式(3)。

1.4 节点的距离路由度量

节点间的距离是影响节点能耗的重要因素。文献[11－13]中分别采用了不同方法计算节点的距离代价。本文所定义的距离度量，如图2所示。将节点Nk距参考点Ox的距离d(Nk，Ox)作为在节点Nx的邻域内，节点Nk的距离路由度量。从式(3)中可以看出，在建立了参考点后的邻域划分模型中，节点距离路由度量这一评价指标的选择，不仅考虑到节点、邻节点和Sink节点所构成的三角形三边的变化关系；同时还考虑了下一跳节点与邻域内特殊位置的距离变化关系。为了避免在路由选择的过程中产生路由环路，规定节点从其邻域划分模型中的前向邻域内选择下一跳节点。为了减少传输跳数，规定节点从其邻域内选择距离Sink节点最近的邻节点作为下一跳。显然在节点的前向邻域内，参考点所在的位置最靠近Sink节点，因此参考点的位置是选择下一跳节点进行数据传输的理想位置。将下一跳节点的选择限定在节点的前向邻域内，在此前提下，图2中各点间的距离满足如下条件(4)。

式中：R0表示节点的初始通信半径。d(Nk，Nx)表示邻节点Nk距节点Nx的距离。由于邻节点在节点的一跳邻域内，所以节点距邻节点的距离d(Nk，Nx)应大于 0且小于 R0。d(Nx，Sink)表示节点 Nx距Sink节点的距离。Area表示整个网络监测区域的面积。当Sink节点位于传感器节点的一跳邻域内时，传感器节点采用单跳通信的方式直接向Sink节点发送数据。对于那些无法直接向Sink节点发送数据的传感器节点，应选择中继节点转发数据。因此设定d(Nx，Sink)的距离大于R0，即只对需要选择中继的节点进行研究。d(Nk，Sink)表示邻节点Nk距Sink节点的距离。由于规定了在节点的前向邻域内选择下一跳节点，所以d(Nk，Sink)应小于 d(Nx，Sink)。 d(Nk，Ox)表示节点 Nk距参考点 Ox的距离。maxDistx表示节点Nx的前向邻域内临界点距参考点Ox的距离。在图2中，点B和点C分别是节点Nx前向邻域内的两个临界点。根据不等式组(4)中的临界条件，当 d(Nk，Nx)＝ R0时，d(Nk，Sink)＝ d(Nx，Sink)，此时 d(Nk，Ox)取得最大值，即d(Nk，Ox)＝ maxDistx。 之后分别将 d(Nk，Nx)＝ R0和 d(Nk，Sink)＝ d(Nx，Sink)代入式(3)中，求得maxDistx的计算公式，如式(5)。

2 MSDRP路由协议

将均方差赋权法引入到无线传感器网络的路由协议当中，将本文所提节点的距离路由度量作为节点路由选择的一个评价指标。结合节点的剩余能量，节点的链路质量，节点的负载等评价指标。分别对节点的评价指标进行数据标准化处理和无量纲化处理，将指标数据的数值限定到相同的数据区间内并消除不同量纲的影响。根据节点不同指标数据的离散程度，利用均方差赋权法对指标的权值进行动态调整。根据目标函数对节点的评价指标进行加权求和，选择目标函数值最大的节点作为下一跳，构建数据传输路径。由于路由决策问题涉及到节点的多个评价指标的综合评判，因此无线传感器网络中节点的路由选择问题可以看作是一个多指标决策问题。

2.1 均方差赋权法的基本原理

对评价指标进行赋权的方法主要有三类，分别是主观赋权法、客观赋权和主客观赋权。主观赋权法是根据主观经验对评价指标赋予权值，如文献[14]中的层次分析法是典型的主观赋权法，它根据专家调研意见赋予指标权值值。客观赋权法是根据评价指标的变化特征，建立数学函数模型计算权值。本文所引入的均方差赋权法属于客观赋权法。

均方差即标准差，标准差是方差的算术平方根。标准差能反映数据集的离散程度。均方差赋权法的主要原理是：各指标相对权重系数的大小，取决于在该指标下各方案评价值的相对离散程度[15]。若各方案在某指标下评价值的离散程度越大，就表明在该评价指标下，各方案的差异性较大，该指标应赋予较大的权值系数，反之亦然。若某指标下各方案的评价值都相同(即评价指标的离散程度为0)，则该指标的权值系数应为0。在无线传感器网络的路由决策过程中，可以将下一跳节点的选择作为一个决策方案。将不同节点的选择问题转化为不同方案的评价决策问题。

通常将评价指标分为“效益型”和“成本型”两大类。“效益型”指标的评价值越大越好，“成本型”指标的评价值越小越好。不同评价指标具有不同的量纲和量纲单位，为了消除量纲与量纲单位的影响，应将评价指标进行无量纲化处理。常用的无量纲化处理方法参见文献[16]。

对于评价值越大越好的“效益型”指标，无量纲化计算公式如式(6)。

式(6)中Cmax，Cmin分别是指标C的最大值和最小值。对于评价值越小越好的“成本型”指标，无量纲化计算公式如式(7)。

2.2 节点的评价指标

本文所提算法将节点的剩余能量、节点的距离、节点的链路质量和节点的负载作为节点进行路由选择的评价指标。各指标的定义和计算方法如下。

2.2.1 节点的剩余能量

所有传感器节点的初始能量都相同，初始能量值为E0。随着网络的运行，传感器节点的剩余能量不断减少。当节点的剩余能量减少到某一限定值时，节点进入失效状态，不再采集数据。对于任意传感器节点Nx，其剩余能量用Ex来表示。

2.2.2 节点的距离路由度量

如2.4节中所述，将节点距邻域内参考点的距离d(Nk，Ox)作为节点的距离路由度量。其度量值可以根据式(3)计算求得。对于任意节点Nx及其邻域内的节点Nk，邻节点Nk在节点Nx的邻域内的距离度量用 Dkx来表示，即 Dkx＝d(Nk，Ox)。

2.2.3 节点的链路质量

数据包传输时的碰撞和拥塞会导致数据包丢失或被延迟转发，因此数据包在被接收时存在时延。因此将节点的数据包传输时延作为节点链路质量的评价指标。通过邻节点数据包确认信息中的时间戳来计算数据包的传输时延。对于任意节点Nx及其邻域内的节点Nk，用Tkx表示邻节点Nk转发节点Nx的数据包的传输时延。

2.2.4 节点的负载

同一节点会接收到来自不同节点所转发的数据。将节点在一个数据传输周期内所接收到的数据包个数作为节点的负载。所谓数据传输周期是指Sink节点接收到网络中所有节点发送的数据所需的时间。对于任意传感器节点Nx，其负载用Lx来表示。

2.3 指标权值的计算

用集合NbZx＝{N1，…，Nm}表示节点 Nx前向邻域内的m个前向邻节点。从集合NbZx中选择一个节点 Nk，则 k∈[1，m]。 在节点 Nx的前向邻域内，节点 Nk的评价指标集用 Cxk＝ {Ek，Dxk，Txk，Lk}来表示。其中Ek表示节点Nk的剩余能量，Dxk表示节点Nk的距离路由度量，Txk表示节点Nk的链路质量，Lk表示节点Nk的负载。

节点Nx的m个前向邻节点构成一个m行的评价矩阵Mx，矩阵Mx中的每一行为一个节点的评价指标集，如式(8)。

分别按照2.1节中所述的“效益型”和“成本型”两种指标类型，对节点的评价指标进行分类。通常节点的剩余能量越多越好，所以节点的剩余能量是“效益型”指标。根据式(6)，对矩阵Mx中表示节点剩余能量这一列的数据进行无量纲化和标准化处理，如式(9)。

式(9)中，maxEx和minEx分别表示节点Nx的m个前向邻节点剩余能量的最大值和最小值，exk表示节点Nk的剩余能量的标准化数据值。如2.4节中所述，对于节点的距离路由度量值，应是越小越好。因此节点的距离度量属于“成本型”指标。同样，对于节点的传输延迟和负载，也是越小越好。所以节点的链路质量和负载都属于“成本型”指标。根据式(7)，分别对矩阵Mx中节点的距离度量，节点的链路质量和节点的负载的各列数据进行无量纲化和标准化处理，如式(10)至(12)。

式(10)中，maxDx和minDx分别表示节点Nx的m个前向邻节点距离度量的最大值和最小值，dxk表示节点Nk的距离度量的标准化数据值。

式(11)中，maxTx和minTx分别表示节点Nx的m个前向邻节点数据传输延迟的最大值和最小值，txk表示节点Nk的传输延迟的标准化数据值。

式(12)中，maxLx和minLx分别表示节点Nx的m个前向邻节点数据传输延迟的最大值和最小值，lxk表示节点Nk的剩余能量的标准化数据值。对矩阵Mx中的数据进行标准化处理后得到标准矩阵STDx，如

式(13)。

式(13)中，由于经过了数据标准化处理，标准矩阵STDx内每个元素的取值范围都在0～1区间。标准矩阵STDx中的各列分别对应节点的各个评价指标。根据2.1节中所述的均方差赋权法，分别计算矩阵STDx中每列指标的平均值和标准差，如式(14)，其中m是节点Nx的前向邻节点个数。

将矩阵STDx中的标准差数据表示为标准差向量 Sx＝{sxe，sxd，sxt，sxl}。 对标准差向量 Sx进行归一化处理，如式(15)。将标准差向量Sx的归一化值作为节点Nx邻域内，m个前向邻节点各评价指标的权值。节点Nx邻域内的权值向量用Wx＝{wxe，wxd，wxt，wxl}来表示。

式(15)中，Sumx是节点Nx邻域内节点评价指标的标准差之和。对于节点Nx，wxe是节点剩余能量的权值，wxd是节点距离度量的权值，wxt是节点链路质量的权值，wxl是节点负载的权值。

2.4 节点的目标函数

无线传感器网络中节点的路由选择问题，是一个多指标综合评判问题。本文采用加权求和的方式对节点的各项指标进行综合评判，即目标函数是对节点指标进行加权求和的计算函数。对于节点Nx，其目标函数如式(16)。

式中：fx(Nk)是节点Nk在节点Nx邻域内的目标函数值。 wxe，wxd，wxt和 wxl是节点 Nx邻域内的各指标权值，如式(16)。 exk，dxk，txk和 lxk是节点 Nk的在节点Nx邻域内的各指标标准化数据，如式(13)中矩阵STDx的第k行。在经过3.3节中的数据标准化处理后，所有指标的数据值都是越大越好。因此节点应选择目标函数值最大的邻节点作为下一跳，如式(17)。

式(17)中，NextHop(Nx)表示节点Nx的下一跳节点，Ni表示节点Ni。其中Ni是节点Nx的m个前向邻节点中，目标函数值最大的节点。

2.5 数据传输与路由维护

位于Sink节点一跳邻域内的所有节点采用单跳通信的方式直接向Sink节点发送数据。Sink节点一跳邻域外的所有节点采用多跳的方式将数据发送至Sink节点。

节点向下一跳发送数据，下一跳节点返回确认信息。下一跳节点继续传递数据，直至Sink节点接收到源节点所发送的数据。当Sink节点接收到网络中所有可用节点的数据包后，就完成了一轮传输。随后Sink节点广播消息宣布开启新一轮的数据传输。

每轮数据传输周期开始之前，节点间都会互相传递剩余能量等链路信息。当节点发现有邻节点电量不足时，就将电量不足的节点标记为失效节点。在进行下一次的路由选择时，排除掉邻居信息表中的失效节点。从可用邻节点中选择下一跳继续传输数据。

2.6 MSDRP路由协议的实现

本文提出的MSDRP路由协议的具体实现步骤如下，其流程如图3所示。

步骤1 网络初始化。Sink节点广播开始消息，所有传感器节点进入初始化阶段。节点通过邻居发现协议探测周围邻节点，创建邻居节点信息表。通过RSSI测距方法计算节点间距离并存入邻居表。

步骤2 数据更新。节点通过无线通信的方式与周围邻节点互相通信，获取邻节点剩余能量信息，节点的链路质量和节点的负载等指标数据并更新邻居表。标记剩余能量不足的节点。

步骤3 数据标准化。节点根据3.3节中所描述的方法，对节点的指标数据进行标准化处理。

步骤4 计算指标权值。节点利用均方差赋权法计算标准化数据的标准差，计算各指标对应的权重值。

步骤5 计算目标函数。节点根据根据目标函数公式计算邻节点目标函数值，选择目标函数值最大的节点作为下一跳。

步骤6 数据传输。节点选择好下一跳后，与下一跳节点建立通信连接。开始新一轮的数据传输。完成一轮数据传输后，节点检查自身剩余能量。如果节点剩余能量不足则进入失效状态，执行步骤7退出网络。否则执行步骤2更新邻节点数据。

步骤7 退出网络。剩余能量不足的节点进入失效状态，不再采集和转发任何数据。

图3 路由协议流程图

3 仿真实验和实际测试

使用OMNeT＋＋5.2仿真环境，对MSDRP协议的性能进行验证。将MSDRP与RPL、EB-RPL在网络能效性、时效性等方面进行了比较；并使用CC2530开发板在实际环境下进行了测试。

3.1 实验参数设置

使用OMNet＋＋对网络协议进行仿真。将100个节点随机分布在100 m×100 m的区域内，Sink节点位于监测区域的中心位置。节点初始能量为0.5 J，数据包大小为 500 byte，控制包大小为 50 byte。节点初始通信半径R0＝20 m。

3.2 仿真结果分析

3.2.1 网络能效性

随着网络的运行和节点能量的消耗，网络中不断有节点因能量耗尽而失效。网络中剩余节点的个数反映网络中节点能量的消耗情况，是评价网络能效性的标准之一。通常将网络中首个节点失效的时间作为网络的生命周期。如图4是网络中的剩余节点个数随仿真时间的变化情况。随着仿真时间的增加，网络中的失效节点逐渐增加，可用节点逐渐减少。从图4可以看出，MSDRP协议与RPL和EBRPL相比，网络生命周期分别提高了55.56%和20.69%。这说明MSDRP协议所采用的权值计算方法能够有效均衡节点能耗，延长网络的生命周期。

图4 网络生命周期对比图

3.2.2 网络负载均衡性

通常除了检测区域边缘部分的少数节点，网络中的大部分节点会接收多个节点的数据并进行转发。由于节点周期的邻节点个数和节点所处的地理位置不同，节点需要接收和转发的数据包个数也存在差异。节点能量主要消耗在发送和接收数据包上，节点的剩余能量标准差可以反映节点之间剩余能量的离散程度，依此对网络中节点的负载均衡性进行评估。图5是网络中节点的剩余能量标准差随仿真时间的变化情况。从图5可以看出，随着仿真时间的增加，节点的剩余能量标准差始终处于上下波动的状态，且波动幅度基本保持在一定范围内。与RPL和EB-RPL相比，MSDRP的节点剩余能量的标准差分别降低了51.11%和33.33%。且MSDRP协议中节点剩余能量标准差的波动幅度较小，这说明MSDRP协议能够有效均衡网络中节点的负载。

图5 节点负载均衡性对比图

3.2.3 网络可靠性

数据包传输时的碰撞和拥塞会导致数据包丢失，无线链路的不稳定也会导致数据包丢失[17]。因此节点的丢包率是反映网络可靠性的一个评价指标。实验中通过改变节点的发包速率，统计节点发送的数据包个数和Sink节点接收的数据包个数，计算出节点的丢包率。图6是不同节点发包速率下，节点丢包率的变化情况。

从图6中可以看出，随着节点发包速率的增加，节点丢包率逐渐增加。当节点发包速率较快时，节点丢包率有明显上升的趋势。与RPL和EB-RPL协议相比，MSDRP协议的丢包率分别降低了75.3%和55.6%。且随着发包速率的增加，MSDRP协议中节点的丢包率上升缓慢。这说明MSDRP协议能够有效均衡节点负载，减少数据包碰撞，提高网络可靠性。

3.2.4 网络时效性

源节点发送的数据和目的节点接收的数据存在时间延迟，时间延迟主要来自于数据包的传输延迟[18]。因此数据包的传输延迟是检验网络时效性的重要指标。图7是不同节点发包速率下，数据包传输延迟的变化情况。从图7中可以看出，随着节点发包速率的增加，RPL和EB-RPL协议的数据包传输延迟呈快速上升的趋势，而MSDRP协议的数据包传输延迟上升趋势较为缓慢。与RPL和EB-RPL相比，MSDRP的数据包传输延迟分别降低了63.5%和42.6%。这说明MSDRP协议结合节点链路质量对指标权值进行调整，能够有效提高网络的时效性。

图7 节点数据包传输延迟对比图

3.3 实际测试

3.3.1 测试环境和节点参数

在面积为100 m×100 m的实验场地上部署测试系统。系统所用节点工作频段为2.4 GHz，节点芯片型号为CC2530，执行 ZigBee/IEEE802.15.4标准，RAM大小为8 kbyte，支持CSMA/CA协议。实验中将10个节点随机部署在监测区域内，其中一个节点作为Sink节点与PC机相连。普通节点采集数据并逐跳发送至Sink节点，Sink节点将数据发送到PC机上。

3.3.2 实验结果及结论

实际环境的测试内容与仿真中所进行的实验相对应，分别对三个路由协议RPL、EB-RPL和MSDRP的网络能效性、负载均衡性、可靠性和时效性进行了对比实验。实际环境测试效果与仿真结果基本一致。进一步验证了MSDRP能够均衡节点能耗，延长网络生命周期。

4 结语

针对无线传感器网络中节点能耗不均衡的问题，本文提出一种基于均方差赋权法的无线传感器网络路由协议MSDRP。该协议将客观赋权法中的均方差赋权法，引入到无线传感器网络的路由协议当中。根据提出的节点邻域划分模型，限定节点的选择区域，缩小节点的选择范围，减少节点的计算量。根据均方差赋权法和邻节点指标的变化情况，

对指标权值进行动态调整。通过目标函数对节点的各项指标的标准化数据加权求和。最后选择目标函数值最大的节点作为下一跳。该目标函数综合考虑了节点的剩余能量、节点的距离度量、节点的链路质量和节点的负载。实验结果表明，MSDRP协议能有效延长网络生命周期，均衡节点能耗。