拍卖机制的包转发路由模型及其仿真研究

徐名霞

广东省高级技工学校 广东 516100

0 引言

在无线传感器网络中，节点的自治性可以使得其在无线传感器网络路由中受到很大的限制。以数据作为中心的信息路由中，查询路由是通过对整个传感数据的命名来进行传播的，每个网络节点中通过建立路由树来传输相应的数据从而更好地降低数据内爆，这样的数据包可以沿着低能耗的路径作为传输以至于更好地降低整个网络的能量消耗。然而，这种路由策略会使得能量消耗不够均衡，从而加速了网络的划分过程，因此，通过拍卖机制的实现包转发路由值得我们研究。

1 拍卖机制的包转发路由模型分析

一个拍卖博弈模型是由两部分组成的：买方和卖方，在整个无线传感器的网络中，买方作为整个发送数据主要节点而卖方则是它的相邻节点。我们需要将多跳的无线传感器网络转换成为一个无向图G =< V，E>的形式，其中V是属于网络中的节点集合，E节点则是它们之间所通信的边集合。假如两个节点存在有边相连时，则说明它们之间是可以直接通信的，要么就无法直接通信，如图1所示。其中ie是属于节点iv所剩下的能量，vih是属于节点iv至Sink节点间的跳数，(,3)vsv h是属于节点s v通过相邻居节点3v到 Sink节点之间的最小跳数。各个节点之间都需要保存局部整个网络的信息，包括了各个节点到 Sink 节点之间的最小跳数以及该节点的余下能量，该节点的相邻节点到Sink节点之间的最小跳数以及这些相邻节点余下的能量。

图1 网络拓扑模型图

Sink节点需要给发送节点之间支付一定的价格以及作为它服务的报酬和发送数据能量所消耗全部补偿；另一方面，为了更好地获得数据的有关转发服务，发送节点也会支付相应的价格给相邻的节点。各个相应的邻节点是为了更好地提高自己的收益需要进行相互的竞标，进行数据包相应的转发服务。假如全部节点是属于诚实的，且当有关节点提高整体收益时其他节点也是乐意进行友好合作的，用包的成功转发率来抑制相关节点的不合作行为，那么整个节点就有可能会得到相关的收益以后拒绝整个转发包又或者是转发少量的包来减少自己现有资源的消耗。

2 拍卖机制的价格路由博弈算法流程

从源节点到 Sink 节点之间选择一条可靠而且相对稳定的路径，提出了一个在无线传感器网络中属于拍卖机制的价格路由博弈算法—Price Routing Game(PRG)。在这样的路由算法中，各个传感器节点都可以看作一个决策者，他们就会依据拍卖博弈模型选择一个适合自己的策略，各个节点也都会按照自己的信息或者相邻节点的信息独立地进行科学决策，给出自已的价格，并且选择一个价格比最合适的价格来提高自已的收益，从而使选择出来的转发节是最优的。

为了使相关节点之间能够顺利实现拍卖，各个节点之间需要获取相邻节点的有关信息和它们到 Sink节点之间的跳数，为各个节点建立起相邻的节点集合列表。第一，网络需要通过Sink节点向其它较为普通节点发送一些广播消息，使得每个节点可以记录通过相邻节点来达到 Sink 节点时的最小跳数。第二，在簇头建立前，各个节点就会向它们的相邻节点间发送能量更新数据消息，记录好它们的相邻节点余下的能量。

当相邻节点建立好列表后，在数据发送的整个阶段，与Sink 节点最远的节点需要相邻节点进行转发服务，各个参与发送又或者是转发数据的节点(买方)都会与它们相邻的节点(卖方)组成一个拍卖博弈过程。卖方为了更好地获得收益需要相互竞争转发一些数据，并给出各自的标价，买方需要根据价格函数是否可以更好地提高自己的整体收益选择最好的节点作为转发数据。如果买方最大化收益的标价相同的有多个时，那么买方就会选择一些能量消耗较少的路径来提高自己的整体收益。整个算法的流程如图2 所示。

图2 算法流程图

3 仿真实验及分析

NS2(Network Simulator，version 2)是属于一种由 UC Berkeley 开发并且成为面向对象的网络仿真器，本质上是属于一个离散事件模拟器，全部的仿真过程都属于由离散事件驱动的，可以很好地实现模拟整个网络的环境。我们可以用NS2仿真软件对 PRG算法进行相应的仿真实验，并且和LEACH 协议与相关簇首改善算法研究对比，表现我们算法能量消耗达到均衡的效果。

3.1 仿真实验

我们所使用的NS2以及Mannasim 来实现该算法，并且分析它的性能，网络中全部的节点基本上都是随机分布的，基站 Sink都处于在整个网络的中间位置，相应的仿真参数设置如表1所示，仿真场景如图3所示。

表1 仿真参数设置

图3 网络场景

我们参考了文献[7]所提供的改进算法—EHDC，并将我们的 PRG 算法与现有的典型 LEACH 协议以及 EHDC 算法作相应的比较。图3与图4分别是属于网络的节点数各为50以及网络节点数为 100 的 LEACH 协议、EHDC 算法和PRG 算法余下的能量图，通过仿真结果我们可以看出LEACH 协议中现有节点的能量消耗比 EHDC 算法以及我们的 PRG 算法速度快多了，而且 EHDC 算法中节点的所需要用能量消耗也都比我们现有的算法(PRG)快一些。可想而知 LEACH 协议中节点的能量消耗与 EHDC 所需能量消耗比我们现有算法中节点的能量消耗要快一些，这是因为LEACH协议以及EHDC 协议是单跳通信的，各个普通节点将相关数据发送给簇头节点就即可。

图4 网络规模为50的单个节点的剩余能量

整个簇头节点再将各个数据以单跳的形式转发给 Sink节点，当某一个簇头节点离 Sink 节点较远时，需要传输能量将会变大，从而导致了大量的能量消耗。因为EHDC 算法在进行簇头选择时是参考节点的余下能量来进行选择的，各个节点需要通过自已现有的余下能量与相关簇内节点平均的剩余能量之比来决定成为簇头的概率，从而更好地均衡每一个网络的能量，因此它比 LEACH 协议会好一些。随着整个网络规模的不断加大，PRG 现有算法的能量消耗也会比其它的算法能量消耗小一些。图5作为整个网络中不相同规模的单个节点的余下能量，从图中我们可以看出来，随着各个网络节点数的相应增加，各个节点的能量将会消耗得越来越多，由于节点越多时其所需要转发或者传输的数据将会越来越多，因此单个节点的能量消耗将会变大。

图5 网络规模为100的单个节点的剩余能量

图6 网络中不同规模单个节点的剩余能量

图7 网络节点数为50的活跃节点总的剩余能量图

图8 网络节点数为100的活跃节点总的剩余能量图

图7与图8是属于在一个较小的时间段较为活跃的节点余下能量的总和，从上图我们可以看得出来，网络中当每一个节点的数量为50与100 时，那么LEACH 协议与EHDC算法中各个活跃节点的总能量就会比我们现有算法中活跃节点的总能量小一些，并且当整个活跃节点的总能量下降的比我们现有的算法快时，那么我们算法(PRG)中各个活跃节点的能量消耗相对来说会比较稳定。在无线传感器网络中各个单跳通信方式来消耗的能量比多跳要高一些，通过多跳通信的方式，并利用相应的博弈模型来选择一个可靠的转发节点，因此相对于 LEACH 协议以及 EHDC 算法来说，本算法能够起到降低节点的能量消耗的作用。

3.2 仿真分析

为了更好地说明我们的拍卖路由博弈算法能量消耗的具有稳定性，我们进行随机挑选了一个时间段内的 10个节点在各个不同网络情况下的余下能量的测试，结果这 10个节点的余下能量情况如图9所示。从图中我们可以知道，随着网络的整体规模的不断加大，节点的相应能量消耗也会随着加大，但是各个节点的能量消耗相对来说会变得比较均衡。图10是整个网络规模为100个节点的最后一轮节点的余下能量，从图中可以知道，LEACH协议中各个节点的余下能量十分不稳定，而 EHDC 算法中各个节点的余下能量比LEACH协议来说会相对稳定多了。由于EHDC 算法是按照能量最大化的节点来选择相应的簇头，而LEACH 协议簇头的选择是具有一定的随机性，因此EHDC算法比 LEACH协议会好很多。LEACH 协议和EHDC 算法的簇头节点之间与 Sink 是属于直接通信的，各个节点之间单跳的通信方式是属于消耗了大量的能量。在我们现有的算法中，各个多跳通信，基本上都是采用博弈模型来选择一个最为可靠的转发节点，而且每一次的转发时所选择的节点是不相同的，因此，我们在整个算法中节点的余下能量相对来说会变得均衡一些，从能量的消耗情况看，在我们的 PRG 算法中节点的生命周期比 LEACH 协议要长一些。

图9 网络规模不同的节点在某一段时间的剩余能量

图10 最后一轮节点的剩余能量

我们的 PRG 算法主要是采用了多跳路由算法，在节点剩余能量方面，与其它两个算法来比具较好的优越性，并且从上图中我们也可以看出 PRG算法中的每个节点的能量消耗也都比较均衡。从另一角度来看，我们的协议的和其它两个协议之间的比较可以知道数据传输时延会有所增加。

4 总结

综上所述，文中建立了拍卖路由博弈模型，并提出了一种进行转发节点选择的价格路由博弈算法流程，该算法流程可以激励各个节点相互合作地转发数据包，每一个节点的目的都是为了通过招标选择最优的转发节点来实现自己最大化的收益。仿真结果表明当前节点的包成功转发率越高，表明该节点的合作级别就越高，越能够提高整个网络的吞吐量。

[1]孙利民,李建中,陈渝.无线传感器网络[M].清华大学出版社.2005.

[2]赵永辉,史浩山.一种无线传感器网络数据包转发的博弈论算法.[J].西安电子科技大学学报.2010.

[3]徐雷鸣,庞博,赵耀.NS与网络模拟[M].北京:人民邮电出版社.2003.

[4]李梦君.暗标拍卖的博弈分析[J].科技创业月刊.2009.

[5]李慧芳,姜胜明,韦岗.无线传感器网络中基于博弈论的路由建模[J].传感技术学报.2007.

[6]杨俊刚,史浩山,杨武.无线传感器网络CSMA博弈优化算法研究[J].传感技术学报.2009.

[7]刘新华,李方敏,旷海兰.基于能量异构的无线传感器网络分布式成簇算法[J].小型微型计算机系统.2010.

[8]宋超,刘明,龚海刚.基于蚁群优化解决传感器网络中的能量洞问题[J].软件学报.2009.