基于加权博弈的传感网路由算法研究*

唐 勇

(广西国际商务职业技术学院,广西 南宁530007)

0 引言

传感网由系列传感器组成,传感器节点感知信息后,通过节点相互转发将信息从感知节点传递到目的终端.[1]由于具备便捷性、易构性、低成本、分布式、自组织等优良特性,被广泛应用于军事、交通、医疗等众多领域.[2]传感节点大多采用电池供电方式,节点能量有限,如何节省能耗以延长节点寿命,是无线传感网络需要着重解决的问题.无线传感网络节点会移动,网络结构不断变化,快速判断网络结构,制定最优路由策略,是节省能量有效途径,也是传感网路由目前研究的热点.

1 传感器路由策略的研究分析

对无线传感网络路由的研究,学者的切入点有很多,研究成果也很丰富.宋海军提出了基于分布式学习的稳定路由策略,[3]策略将源节点到目的节点的路径看成多约束条件的路径,利用约束算法优化路径,优化了端到端的传输质量.尚亚丽提出了基于能效传播路由,[4]利用期望能耗来判断转发集结点,减少评价发送能耗和无效发送,提高了传感设备生存时间.苏凡军提出了基于信任度的节能机会路由算法,[5]利用节点间的信任度,减少恶意节点的联通和恶意行为,提高了传输效率.陈明明等人提出了能耗均衡路由算法,[6]利用邻居节点的剩余能量和位置,限定了参与路由的节点数量,节省了能量.崔亚楠等人提出了基于粒子群最优算法的LEACH(Low Energy Adaptive Clustering Hierarchy)的改进路由,[7]对经典分簇算法进行了改进,提高了路由效率和效能.林勇提出了基于链路质量的无线传感网络路由算法,[8]综合考虑发送时延和发送质量,将两者联合起来,形成了一个混合路由.胡春安提出了基于鲸鱼算法的无线传感器网络分簇路由算法,[9]形成了一个更加合理的簇头——能量模型,减少了簇头交换的频率.任秀丽提出了一种无线传感网中数据传输延时优化的路由协议,[10]将有效探测占比与传输效率作为节点传输有效性,通过传输有效性来控制优化传输的发送排队,从而达到优化整个网络的目的.

当代学者从不同的角度对传感网路由进行了优化,从优化结果来看,大多优化了单方面或者两方面的指标,对多个指标同时优化尚缺乏对策.

2 公平博弈的传感网络路由算法

2.1 参数定义

2.1.1 公平性

在传感网络中,公平性是指节点或者数据流公平使用信道转发信息能力的比值,定义为FI(Fairness Index).

公式(1)中,T f为节点f的吞吐量,w(f)为权值.权值越大,需要获得的更高发送权限.当FI的值为1时,实现绝对公平.

2.1.2 节点流服务指数

2.1.3 节点平均服务指数

S n是指节点n平均服务指数,是周期时间内m条流的加权平均.

2.1.4 邻节点平均服务指数

AS n值指在t1至t2时间段里,节点n的所有邻居节点获得的平均服务指数.

通过公式(1)～(4)可以推算,如实现了局部公平.|S n-S m|=0,实现了全局公平.

2.2 基于博弈论下的发送概率

在博弈论模型下,在无线传感网中,如只有节点i发送信息,节点i成功占用信道,则其收益为A;若除站点i外,其他N-1个节点同时向某节点发送信息,信道产生冲突,则i的代价为B,若此时i选择不传输,则收益为节省的能量减去传送的机会的代价,记为C,则站点i的效益函数为:

根据文献[11]表明若站点采用随即退避机制接入竞争,接入概率为:

其中,m为最大退避级数,CW为竞争窗口.

P c(α-i)为站点i的条件碰撞概率,

2.3 退避时间

一个节点n的m条流,如果流i的S in过大,则说明流i获得了更多的发送权,对于其他的数据流来说不公平,可以提高此流的退避时间来降低流i的竞争力,实现节点n的局部公平性.相反,如果流i的S in过小,则缩短它的退避时间来提高流i的竞争力.同时,一个节点的S n比AS n大,此节点大整体竞争能力过强,延长节点退避时间降低竞争力.

在一个节点里,对于每个流的退避时间:

在公式(5)中,B代表退避基数时间,所有流的值都相同.随着信息流发送,竞争不断推进,出现了竞争不公平现象,节点流利用公式(6)调整S退避时间,实现公平竞争,整个网络达到纳什均衡状态.

2.4 基于加权博弈的算法机制

本文WGRA(Weighted game routing algorithm)算法机制如下:

(1)每个传感节点维护一张路由表,表里包含id,Sin,Sn和ASn等参数.邻居节点相互传输交换Sin,用Sin参数调节退避时间.为了节约开销,Sin不单独传送,Sin嵌入发送的数据流中.

(2)开始时,所有的流、节点的竞争力都相同.节点每隔一个周期,统计本身每条流的服务指数Sin,计算节点Sn和ASn参数的值.

(3)当FI=1时,已经实现绝对公平,所有节点按照当前退避方式进行退避,不另行调整,直接跳转到第(6).当FI≠1时,进入第(4).

(4)与邻居节点交换Sin,Sn和ASn参数.为了节约信息开销,算法只在以下3种情况下触发交换机制:①Sin,Sn和ASn的值出现了变化时.②邻居节点出现变化.③达到了信息交换周期最大值.

(5)利用退避时间公式BT=B×(1+S)×α*i,计算节点和流退避时间,调整竞争力.当FI=1时,跳转到第(3).

(6)退避时间到,节点发送信息.

(7)簇节点周期时间T 进行簇头重新选举,剩余能量最多者当选为簇头.

3 实验仿真

利用NS2(Network Simulator Version 2)对WGRA 算法进行模拟分析.主要仿真参数见表1:

表1 主要仿真参数Tab.1 Main Simulation Parameters

为了进行对比研究,选取文献[12]可靠能效路由和文献[13]时延路由进行对比,主要分析平均能耗、网络寿命、平均传输次数、端到端延时、数据包传递率5个方面的性能指标.

3.1 平均能耗

三种算法的平均能耗如从图1所示,WGRA 平均能耗相对于REER 和DETR 更低,原因是WGRA算法采用了竞争博弈算法.依照博弈论,当系统达到纳什均衡点时,系统的利益达到最大化.REER 通过能耗最低节点进行转发,但能耗最低的节点转发时,存在信道竞争失败情况.而DETR 算法主要是优化时延,能耗相对较大.

3.2 网络寿命

网络寿命与能耗息息相关,在能量定量情况下,能耗越高的网络寿命越短.两者之间非线性关系,传感网中所有信息节点非持续性的定量地发送信息,网络结构也非持续性稳定不变.从图2看出,WGRA 综合耗能最低,其网络寿命时间越长,而REER 算法综合耗能较高,网络寿命较短.

图1 平均能耗对比Fig.1 Average energy consumption comparison

图2 网络寿命对比Fig.2 Network life comparison

3.3 平均传输次数

在WGRA 算法中,首先考虑到信道的使用公平,通过相互博弈,局部和全局的加权最公平,使得信道有效利用率较高,无效探测较少,实现了平均传输次数较少.DETR 算法从传输路径考虑,REER 算法从能量约束的条件下考虑,平均传输次数与能量相关,REER 在一定程度上优化了平均传输次数,REER 的平均传输次数比DETR 的传输次数少.平均传输次数对比见图3.

3.4 端到端延时

从图4可以看出,WGRA 算法在延时方面也有较好的性能.端到端延时跟信道有效利用率有密切关系,WGRA 通过博弈算法使信道使用达到了最大值,无效发送比率降低,信道拥塞程度降低,端到端延时较少.REER 算法对延时没有特殊处理,DETR 算法通过优化路由,缩短了路由距离,端到端延时相对REER 算法较好.

图3 平均传输次数对比Fig.3 Comparison of average transmission times

图4 端到端延时对比Fig.4 End to end delay comparison

3.5 数据包传递率

WGRA、DETR 和REER 数据包传递方面的性能见图5.WGRA 的数据包传递率相比DETR 和REER更具优势,数据传递率与信道有效利用率和传输距离有直接关系,信道有效利用率越高,数据传递率越高;传输距离越短,传递率越高.节点数据越多,节点越密集,传输距离越短,数据包传递率越高.

图5 数据包传递率对比Fig.5 Packet delivery rate comparison

4 结语

针对无线传感网络路由,引进博弈论使节点通过竞争以到纳什均衡,从而实现节点对信道利用的最大化、能耗最小化,达到优化路由的目的.近些年,学者对无线传感网络路由问题的研究有了新的方法,主要是引进一些智能算法,使路由算法能实现自我学习、自我调节,从而达到优化路由的目的,这也是未来一段时间的研究热点.