基于优化模型的协作通信的中继节点选择算法*

蔺 莉,宋三华

(黄淮学院信息工程学院,河南 驻马店 463000)

无线传感网络WSNs(Wireless Sensor Networks)已广泛应用于工业自动化系统[1-2]。然而,通常工业厂房常伴有噪声以及障碍物,这影响了传感节点的数据传输性能[3]。而协作分集技术是提高数据传输可靠性的不错选择。这些技术充分利用了无线媒介的广播特性,使部分节点承担中继节点的作用。

协作重传是提高消息传输成功率的有效技术。而协作重传技术的性能依赖于中继节点[4-5]。这些中继节点实时监听消息,为后续协作重传做准备。因此,协作通信的性能取决于中继节点的选择。若将网络内所有节点均作为中继节点,固然可提高了协作分集的参与率,但这必然浪费了带宽和能耗。据此,协作重传技术的关键在于如何选择最合适的节点作为中继节点,进而提高数据传输的可靠性[6]。

目前,研究人员提出不同的中继节点选择算法,如基于链路质量、基于节点剩余能量。此外,文献[7]提出基于总体随机选择中继节点算法TRT(Totally Random Technique),但是此算法并没有考虑节点与协作者间的通信质量。而文献[8]提出了基于随机邻近协作者算法RAC(Random Around Coordinator),即从协作者邻近的节点中随机选择一些节点作为中继节点,并结合RSSI指标。此外,文献[2]采用机会选择中继节点算法OSA(Opportunistic Selection algorithm)。此算法依据网络误差率选择中继节点。

此外,国内研究人员对协作通信的中继节点选择也进行了大量的研究。苗春雨等[9]利用启发式算法寻找中继节点的最优位置。而赵玉丽等[10]利用信道系数选择中继节点,但是该算法通信开销较大,需不断地获取信道系数,尤其是大型的移动传感网络。而孙利娟等[11]利用误码率和节点位置信息,并引用分布式竞争机制产生中继节点。王宁等[12]面向簇类的传感网络,依据节点剩余能量和节点位置信息,并利用改进的粒子群算法选择中继节点。但是,引入粒子群算法加大算法的运行时间,增加节点的能耗。

为此,本文提出基于优化模型的协作通信的中继节点选择OM-SRN(Optimization Model-based Selection of Relay Nodes)算法。与现有的中继节点选择算法不同,OM-SRN算法将中继节点的选择问题进行基于增益函数的优化问题处理。OM-SRN算法依据节点的邻居节点数、剩余能量以及链路质量三方面信息选择中继节点。最后,通过实验仿真分析了OM-SRN算法的性能。本文的主要贡献可以归纳为两点:①将中继节点的选择问题模拟成优化问题;②不是简单地采用随机选择中继节点,而是通过节点的邻居数、能量和链路质量信息综合择优选择中继节点。即利用这三方面的信息对的中继节点的选择进行约束。

1 能量模型

采用如图1所示的能耗模型[12]。收/发两端相距dm。若d较短时,采用自由空间传输模型,而对于d比较大时,采用多径衰落信道模型。若在相距dm,发射端向接收端传输q比特消息所消耗的能量:

(2)

式中:Eelec运行发射器元件时每比特所消耗的能量。Efrris、Etworay分别表示发射器在自由空间、双径传播模型(two ray ground model)的单位功率放大器的能量消耗,并且do:

(3)

相应地,对于接收q比特的消息所消耗的能量:

ERX(k)=qEelec

(4)

2 OM-SRN算法

2.1 优化问题的建立

OM-SRN算法将中继节点的选择进行优化问题处理。通用的优化问题的数学表述,如式(5)所示:

minimizef(x)
subject to:
g(x)≤0
h(x)=0
x∈χ

(5)

式中:f为目标或增益函数。而g和h为约束函数,其限制了可行解的空间。而x:(x1,x2,…,xn)是可行解矢量,其中最优解表示为x*。

函数f(x)是优化问题的关键,其决定了矢量x。为此,中继节点的选择由式(6)所示的增益函数表示:

(6)

式中:Gi表示节点i的增益。ni表示节点i的邻居节点数。

而ei的定义如式(7)所示,其反映了节点i的剩余能量归一化值。

(7)

式中:REi、IEi分别表示节点i的剩余能量和初始能量。

而si的定义如式(8)所示:

(8)

式中:RSSIj表示节点i的邻居节点j的RSSI值。而Limited_RSSI为常数,表示通信的RSSI的最小值(-87 dBm[13])。

而Hi的定义如式(9)所示,其反映了成功传输数据的历史数据。

Hi=(1-α)Hi+αSR

(9)

式中:α为控制参数,可依据不同情况调整α值。如果成功传输了数据包,则SR=1,否则为空。

此外,式(6)中的βn、βe、βs和βH分别表示ni、ei、si和Hi的权重。式(5)所示的目标函数f考虑了邻居节点数、数据传输成功率、信号强度和节点的可用能量。

为了使中继节点数最小化,并保证同时每个节点均有一个转发节点。将式(5)所示的优化问题转化为:

(10a)

subject to:Ax≥b

(10b)

Cx=d

(10c)

xi∈{0,1}

(10d)

式中:N为总体节点数。式(10a)为目标函数,函数值越小,节点成为中继节点的概率越低。式(10b)中的A为邻接矩阵,且尺寸为N×N。第i行第j列的元素值表示为ai,j。若ai,j=1,表示节点j是节点i的邻居节点,否则ai,j=0。如果协调者没有收到节点i的邻居节点列表,则矩阵A的第i行的元素值均为零。

而x为N×1维的矢量,如果节点i是它邻居节点,则xi=1,否则为零。b是一个矢量,其元素值bi表示每个节点的最小中继节点数,且至少设置为1。

式(10c)是由协调者设置的约束项,其中矩阵C表示与协调者没有足够通信链路的节点集。矩阵C的每一行表示作为节点i的中继节点的候选节点。

式(10)的优化问题将中继节点设置最小增益。由于采用了二值变量,则式(10)所示的优化模型为二值整数规划BIP(Binary Integer Programming)问题[14]。由于BIP问题是NP-Hard,可采用Branch 和Bound算法求解。

2.2 OM-SRN算法的执行过程

当节点加入网络,就在每个beacon间隔内广播beacon 消息。一旦接收到其他节点的beacon,就将其作为自己的邻居节点。同时,各节点计算自己的增益值(式(5)所示),然后,再将这些值传输至协调者。协调者再通过式(10)选择中继节点。一旦接收了中继节点,协调者就在下一个BI时隙内将这些中继节点信息公布,使得节点知道是否成为中继节点。

一旦产生了中继节点,就开始数据传输阶段。通信阶段由传输和重传阶段。在第一阶段,各节点开始传输数据,如图1所示。每个节点传输了它的消息后,中继节点就存储它所监听的消息和发送节点的ID。如果节点不是中继节点,当它完成了数据传输后,就进入休眠。

所有节点完成了第一阶段的消息传输后,就监听邻居节点所传输的消息,进而更新邻居节点集,进而识别协调者。

在第二阶段,每个中继节点重传消息,其包含了协调者所存储的ID号。如图2所示,节点N2重传消息。

图1 节点传输消息示例

图2 重传消息阶段

3 性能仿真

3.1 仿真环境

为了更好地分析OM-SRN算法性能,建立仿真平台。考虑了50 m×50 m仿真区域,且协调者位于仿真区域中心。利用混合整数线性规划MILP(Mixed Integer Linear Programming)求解优化问题。仿真时间为450 s,在这个仿真时间内,协调者发送50个beacon。其他的仿真参数如表1所示。

表1 仿真参数

此外,选择总体随机选择算法TRT、协调者的随机选择算法RAC、机会选择算法OSA作为参照,并考虑消息传输成功率、每个节点的平均协作传输的消息数以及冗余消息数三方面的性能。

3.2 数据分析

首先分析消息传输成功率随节点数的变化曲线,如图3所示。

图3 消息传输成功率

从图3可知,所有的采用中继节点技术的算法比没有采用中继节点技术的算法具有更好性能。而与其他算法相比,提出的OM-SRN具有最高的消息传输成功率,原因在于:OM-SRN能够合理地选择中继节点,使得消息传输效率更高。

图4显示每个节点的平均协作传输消息数。从图4可知,OM-SRN算法具有最小的平均协作消息数。协作传输消息数越少,说明所选择的中继节点数越少,降低网络成本。结合图3不难发现,提出的OM-SRN算法以较少的协作节点完成最高的消息传输成功率。

图4 每个节点的平均协作传输消息数

最后,分析了冗余消息率随节点数的变化情况,如图5所示。从图5可知,当节点为800时,OM-SRN 算法的中继节点所产生的冗余消息率接近于零。而TRT算法具有最高的冗余消息率,原因在于:它随机选择中继节点。

图5 冗余消息率

最后,分析算法的能耗性能。节点的初始能量为0.5 J,Eelec=50 nJ/bit、Efs=10 pJ/(bit·m2)、Etworav=0.001 3 pJ/(bit·m4),节点数为81。同时,引用网络生存时间、稳定时长表征能耗。网络生存时间是指网络内最后一个失效节点所发生的时间;稳定时长是指网络内第一个失效节点所发生的时间。因此,网络生存时间、稳定时长越长,能耗越低。实验数据如表2所示。

表2 能耗性能

从表2可知,提出的OM-SRN算法的稳定时长和网络生存时间略低于其他的三类算法。这些数据表明,OM-SRN算法的平均能耗高于OSA、RAC和TRT算法。原因在于:OM-SRN采用分布式竞争机制,并需要收集相关信息,加大了通信开销,消耗了节点能量。

4 总结

合适地选择中继节点是提高WSNs数据传输质量的关键。提出的OM-SRN算法将选择中继节点问题进行优化模型处理。同时,考虑多个因素选择中继节点。实验数据表明,提出的OM-SRN算法在消息传输成功率、冗余消息数方面的性能得到提高。这些数据表明,OM-SRN算法在选择中继节点方面的优势,即以最少的中继节点数实现可靠的消息传输性能。

然而,节点能耗较大,后期,将进一步优化算法,降低能耗。此外,本文仅通过实验分析了算法的性能,后期将扩展算法的应用场景,如高速移动的车联网,分析算法的实时性。