GTDM: DTN路由在非合作的博弈理论在城市环境

文摘

延迟容忍网络(dtn)的性能可以通过运动模型的影响在不同的应用程序环境。现有的dtn路由算法不能满足当前城市环境中由于节点密度之间存在较大的差异,社会特征,和有限的能量。dtn的关键指标如成功交货率、平均交货延迟,网络的生命周期和网络开销比例可以影响公民dtn应用程序的性能。旨在提高dtn的关键指标在城市环境中,提出了一种基于固定水槽站结构和更适当的路由算法基于博弈论的决策(GTDM)命名。GTDM显示了社区选择决策过程和包交付策略基于非合作的博弈理论方法和城市环境特征。GTDM性能评估使用数值模拟在工作日运动(WDM)模型,结果表明,GTDM优于其他传统dtn路由方法,流行和先知等算法。

1。介绍

延迟容忍网络(DTN)是成千上万的资源受限的移动传感器网络通信在一些具有挑战性的环境。dtn的特点是高延迟交货率低,长时间分离的因为网络拓扑变化不断。近年来,使用dtn在大都市地区吸引了越来越多的关注1- - - - - -3]。在未来,“智能”城市可能由基本的公共服务使用尖端的计算机技术(4),这主要是DTN平台上实现。不像在其他环境中使用,如战场,空间,和海洋(5- - - - - -7),有更多的机会与便携式智能设备的快速发展。DTN路由问题是讨论基于不同的要求不同的部署环境和应用程序。虽然有一些现有DTN路由算法,可以应用于城市环境,表现不佳影响城市基础DTN系统的效率。因此,我们专注于改善DTN性能在城市场景;更高效的路由算法是专为移动节点约束能量。在本文中,我们提出一个框架的传感器选择基于博弈论的方法和数据队列管理的优化,可以找到一个平衡和能源消耗比流行和先知路由算法有更好的网络性能。本文的主要贡献如下。(1)我们描述了分布式固定水槽站数据收集和移动节点作为数据源的作用或中继节点在城市环境中。然后,介绍了邻居节点选择方法。(2)一个数据包交付决策算法GTDM dtn提出了基于博弈论的方法。dtn路由确定的城市环境。GTDM可以决定惩罚或奖励的一对节点之间通过一个游戏,可以测量和活跃节点通过节点的资产。(3)两个节点之间的数据包优先级和数据包传输策略存在;通过这种方式,一个数据包确定哪个节点是最适当的包。(4)该算法的性能是由一系列的实验验证下WDM运动模型。结果表明,GTDM可以延长网络的生命周期,并更好的路由性能比先知大多流行和路由算法。

本文的其余部分组织如下:部分2描述了相关的作品基于城市环境的路由算法和部分3描述了合适的场景和GTDM算法过程。节4本文给出了基于博弈论(GT)的转发决策。节5我们目前的仿真设置和结果,和本文的结论部分6。

2。相关工作

DTN协议应当保持谨慎的态度如何节省有限的网络资源。所以,数据包传输中继节点,不当会导致网络性能的下降。然后,如何判断一个节点发送数据包到另一个节点?在某些情况下,GT可以应用于解决此类问题8,9]。一般来说,有两种类型的GT:合作博弈理论和非合作的博弈理论。合作博弈理论更关注小组通过合作努力的最大利润。一个节点将自私通过最小化个人效用在分布式的决策环境。非合作的博弈理论专注于每个节点的个人效用,和更少的关注整个dtn的效用。非合作的方法不需要全球知识节点。相比之下,在一个合作方法,节点与合作GT必须同意premediated策略和参与者全球知识(10,11]。移动节点需要大量的通信维护成本为全球知识合作方式;因此,dtn与完整的全球知识是不现实的现实。考虑到以上,游戏配方设计应采用非合作的博弈策略使他们更为现实。

基于相同的考虑,El-Azouzi et al。12)提出了一个非合作的博弈方法,在源和目标节点包含在两个部分重叠的区域。作者流行路由算法用于大量的节点。dtn的流行转发算法最大化的概率成功的数据交付。然而,它忽略了两人之间的关系的存在在城市环境。例如,两个同事会整天工作,导致移动节点重复接触(13]。此外,我们相信,有活动对象和活动对象在城市环境中(14]。前对象将有更多接触机会比不活跃的对象,和主动传感器载体是合适的中继节点。除此之外,移动节点在城市环境中运动规律和周期性的接触;可以预期遇到历史的规律。不幸的是,这些条件没有考虑的常见DTN路由算法。因此,大多数现有的路由算法不工作在城市的最高效率。关注转发路由模式的决策问题,先知是一种概率路由协议使用past-encounter历史和老化方法转发决定,是一种最常用的dtn路由算法。显然,先知路由算法没有考虑所有社会关系的特点和在城市环境中行人的例程。同样,流行路由算法在有限的资源情况下不能释放能力。因此,我们提出了一个更加实用和有效的GTDM-based路由算法,它考虑的各个方面的城市环境中,这是一个更灵活的和可扩展的DTN路由算法对于城市环境。

3所示。GTDM路由算法

在城市环境中,每个节点的交付能力是不一样的,因为移动范围的限制和个人的规律性。和GTDM是专为高能力节点选择历史评判的游戏过程。因此,适用于一些场景与普通移动节点。基于游戏的DTN的移动节点被认为是游戏的参与者和必须遵守的规则设计机制。使用激励机制,提供的转发节点和行为不端的节点受到惩罚的机制。此外,任何传播行为应该谨慎;毫无意义的也转发节点消耗的能量。显然,洞的能量将减少DTN的性能;因此,能量平衡在GTDM应该需要考虑。

3.1。移动节点和固定水槽站在城市环境

当DTN部署在城市环境中,它可以用于数据采集。因此,移动节点应该是数据生成器和传递载体。移动节点通常代表行人、车辆传感器载体。此外,一些静态站点数据收集器位于节点密度高的地区。它被描述为固定水槽站在这篇文章中,我们提出了在文献[15]。移动节点和固定站是现实的方案应用在城市环境中。例如,范教授和Fdida [16)建议dtn可以帮助新闻的分布在城市通过使用固定节点。另一个实例,发现恶意行为通过使用不当行为检测系统(MDS)提出了改善网络性能,而且在大城市的车辆dtn讨论郭et al。17]。这些描述应用程序之间有一些共同的特征,如节点运动轨迹和定期运动。轨迹可以重叠的高密度路径区域以最小的成本和与给定的环境地图。此外,工作日运动(WDM)模型描述了人们在城市的动态行为18]。因此,我们相信,移动节点有很多接触的机会在更高的道路密度地区,水槽和固定站适用于分布式位置在这样的地区因为这个规律。这样,dtn可以灵活调整固定站和固定位置的数量来实现所需的性能。此外,区域内移动节点有一定的运动规律和活跃节点可以选择的历史记录。从我们上面提到的,路由算法设计应该基于这个场景的特性。

3.2。GTDM算法流程

GTDM的想法是建立一系列的策略决定。在每个节点建立多个指标;在游戏过程中这些指标的变化不断和交付的历史。然后,一些决定顺序。

GTDM路由算法的细节描述如下。

GTDM遵循范式三个数组dtn的游戏代表游戏。在这里,是一个有限集的移动节点,目前有有效的连接。策略集空间被描述为,在那里表示节点的策略选择。该策略组合,策略代表节点的选择和其他的选择吗移动节点。是移动节点的支付函数,它的定义是。在这里,奖功能和吗是惩罚函数。

dtn的移动节点是游戏的参与者,不知道整个拓扑和节点或网络参数。每个移动节点建立一个度量列表成功交付,其中包含的节点列表,硬币计数、资产价值,剩下的缓冲区大小和能量水平。列表移动节点支持实时更新。的值和精力的节点在列表计算公式(1)和(2)如下: 在哪里代表累积包交付时间的统计数据,是目的地址设置,是事件计数函数 在哪里是节点的初始能量。能源消费函数描述。

移动节点连续扫描的邻居。路由过程开始一次移动节点的数据包。如果节点发现邻居节点在通信区域,节点的邻居集建立有限。然后,包交付的第一阶段开始,它包括两个步骤。

步骤1。节点遍历的数据包发送缓冲区是否属于一组包的目的地。如果数据包的目的地属于一个邻居节点、节点会直接发送到吗。GTDM,每个数据包的目的地是一个固定的水槽。另一方面,GTDM只会进行扫描,当邻居。

步骤2。目的地的数据包属于集重新安排增加TTL值,根据这个顺序传送。

在第二阶段,节点选择一个邻居的中继节点集将剩下的包。节点选择GTDM取决于资产的竞争博弈论的节点。它满足相应的支付函数为。GTDM设计中,资产定义如下: 在哪里服从指数分布。奖励因素和吗代表资产的变化强度。是奖励函数,是惩罚函数。的节点最强大的资产被选中。一旦决定,每个节点无法找到行为是否影响整个效率,因为每个传感器不了解网络。

在你的邻居节点被选为一个代理节点,节点将有选择地传输其余数据包第二遍历发送缓冲区。的节点然后决定哪些数据包将被传送到代理节点使用multidecision方法。这个过程描述如下。

步骤1。首先比较的能量水平、节点将停止提供数据包如果条件是满意的。如果不满足此条件,节点将继续第2步。

步骤2。每个等待数据包的节点与计算节点综合运输重量。在这里,的节点计算如下: 在哪里,是重量因素。在这里,代表了数据包的目的地址。的概率是交付比例。它所代表的两个节点更有可能成功地交付包和计算公式(5)。代表了自由缓冲系数函数,可以由公式(6): 在哪里代表节点的缓冲区大小。更高的值表示更高的承载能力。

步骤3。在第二遍历每一站,GTDM决定是否节点传输当前数据包根据其综合运输重量。节点将被允许传输数据包如果条件是满足。

当节点发送一个数据包到代理节点,它代表一个节点的失败在游戏中,节点由函数的惩罚吗。同样,节点赢得了比赛,这是奖励的函数。,计算如下: 资产价值改变了每个节点的函数(4交付后)的决定。有两种遍历小区选择和数据包在GTDM选择;GTDM的时间复杂度。

4所示。基于GT的转发策略

在本节中,我们目前的转发策略时使用有两个节点基于GT。游戏理论是一种有效的数学描述解决冲突self-decision-making球员之一。与GTDM算法不同,常见的GT认为两个移动节点作为个人谁能拒绝别人的包。这种行为增加了算法的复杂性。后决定是决定使用GT方法,节点传送数据包。移动节点的传输范围在城市环境中可能会覆盖几个节点由于人口密度特征。在GTDM,集被定义为一个有限的节点集覆盖。发送节点(SN)广播信息接收者节点(RN),从集合中选择是哪一个由竞争的方法。资产函数表示节点的高效运作并由两部分组成。奖励函数允许节点为赢得比赛获得利润,而成本节点时失去的惩罚函数。

在dtn部署在一个城市,行人节点定期与WDM在一个相对较小的区域移动,和每个节点数据包的目的地址可能属于不同的固定站。在这种情况下,节点必须提供每个包一个适当的继电器。换句话说,数据包将选择一个继电器更可能成功交付包或等待更好的机会。

图1表明活动的行人区域相对较小,而行人例行。基于前面的假设,如果节点或节点已经实现了数据包成功修复站、水槽站附近将其中一个或两个在波分复用。我们计算交付概率比例解决的问题是否节点将传输节点的包吗。根据上述因素,这种策略决定是否传输数据包或等待一个更好的竞争对手。

假定值的SN代表0的转发决定和一个值代表转发的放弃。一个RN值1表示接收和接受的一个RN值0表示失败。总结的策略和资产SN和RN, GTDM的支付矩阵如表所示1。

从这,我们可以逐渐排斥非活动节点。在这个游戏中,我们使用纳什均衡的RN传播的决定。

选择过程当RN选择0:如果SN选择0,将得到的值0。当SN选择1,它会。很明显,然后SN应该选择1。当RN选择1:如果SN选择0,将得到的值0。当SN选择1,它会。很明显,,然后SN应该选择1。平衡是,这意味着SN和RN鼓励执行传输和接收。它是一个纯策略纳什均衡。

5。仿真和结果

5.1。仿真设计

机会网络环境(一)模拟器19)选择实现GTDM算法。GTDM之间作比较和现有DTN路由算法,如流行和先知算法。

几个假设与模拟相关联。首先,行人、公共汽车、固定站,和出租车都代表一个不同的节点类型。行人节点能量有限,运行在一个定期。使用能量模型中(19),能量受限的移动节点是基于能源预算方法和能源消耗一个节点可以表示如下: 在哪里代表了能源消耗与节点相关的扫描。是传输能耗每秒发送消息时。是每个扫描响应的能源消耗。其他类型的节点没有权力约束由于恒定的电源。

其次,移动节点的数据源和中继节点转发数据包到固定的水槽。六个固定电台节点分布密度相对较高的路径与城市环境(图2)。

第三,为了尽可能准确地模仿“现实世界”的环境,遵循WDM每个移动节点运动模型。商店的WDM包含位置信息,房屋,和办公室。移动节点的居住时间在任何一个位置控制的机制是一样的。赫尔辛基市区地图作为部署目标。其他城市地图提供的细节是一个模拟器(19]。

5.2。主要仿真参数设置

在这个模拟场景中,行人节点移动经常在商店中,房屋,和办公室。这些节点控制的WDM的数据集,提供的是一个模拟器。模拟场景的关键参数如表所示2,假定GTDM仿真的关键参数如表所示3。

我们应该注意我们应该获取合理的参数。例如,移动设备通常配备蓝牙模块,因此行人的传播范围是10米。

5.3。仿真结果

DTN的性能会受到许多因素的影响如节点密度、数据包大小和缓冲区大小。一般来说,更多的节点让我们遇到更多的机会,然后游戏*节点密度高的节点密度低的多。因此,我们观察GTDM不同密度条件下的性能。

dtn的交货率是重要的指标;更好的算法应该有相对较高的交货率。交付率的三个算法以同样的参数和设置如图3。我们发现GTDM的交货率与节点密度的增长比流行或先知。在节点密度低,没有一个明确的交货率差别先知和GTDM算法;更有可能的是邻居只有一个节点,它不能完全参与节点选择的竞争。GTDM dtn时具有更好的性能比其他算法在节点密度高。流行算法最坏性能由于其有限的缓冲区大小和未转发。

dtn的开销成本比率是另一个重要性能指标。DTN路由算法设计的目的之一是降低网络开销成本,这导致大量的数据包副本。的开销比是描述为重复率。更高的开销比导致较低的DTN交付效率。的开销比计算如下: 在哪里介绍了传输时间和成功是成功的交付时间。如果等于零,这意味着每个传输行为是一个完美的交付过程。

的开销比GTDM优于其他两种算法(图4)。流行和先知算法的开销率变得更高随着节点密度的增加,这意味着节点不能做出有效的决策,更多的机会变得可用。

数据包的数量会随着时间推移而增加。WDM捕捉现实生活场景的运动特点,给予更多的接触机会的高峰人群。定期的接触概率随时间的变化(图5)。先知算法没有考虑这么长时间。适当的传输机会将错过,因为随着时间的预测价值减少。同样,流行算法转发太多包在低数量的接触时间。所以,这种行为导致的开销比高于其他人。

交付的可预测性影响决策和先知的算法受到不断老龄化的影响。例如,即使一个节点有能力提供一个包店,其在办公室工作时间可能更长。在这种情况下,降低随着时间的推移,这可能会导致失去一个交付的机会。因此,先知不是一个合适的算法对城市环境。由于WDM运动的特点,延迟平均曲线的趋势波动的三个算法(图6)。结果表明,延迟平均GTDM小于流行或先知。

我们发现110 -节点生存状态下的城市场景。大多数节点是死在流行时间298800秒(图7)。其余的节点不能维持正常的系统的性能。

同样,大多数节点排气能量在同等条件下与先知算法(图8)。先知的存活节点更比流行路由。

从图9,显示的生存节点GTDM算法比其它算法。很明显,在流行路由,节点发送数据包到任何节点可能接触到和无限的洪水算法将不断浪费能源。先知算法将数据包传输到一个节点交付概率相对较高,但它是被老化的常数。因此,有组织的节点有一个类似的很长一段时间后交付低概率;因此,很难确定中继节点。一些节点传输的数据包给他人传递概率相对较高在一段时间内,然后是潜在的节点将会很快消亡。显然,层叠的效果会出现缩短dtn一生。

为了验证GTDM的能量平衡,能量计算样本方差随着时间的流逝 在哪里代表了样本均值和是能量样本值。一个更高的在节点值表示更高的能源缺口,这可能导致某些节点过早死亡。从图10,这是表明GTDM算法能够很好地平衡移动节点的能量消耗减少失败节点的数量,延长网络的生命周期。

6。结论

目前,DTN路由算法适合城市环境是最重要的主题之一,它吸引了很多学者的关注。我们提出GTDM算法,传输的路由算法基于博弈论的决策。GTDM框架,实现几个操作调整传输队列和确保适当的节点选择合适的传送数据包。间接费用比率、能源消耗和平均延迟GTDM最小化通过比较流行的算法和先知。等仿真结果的WDM交货率和网络寿命,支持GTDM流行和先知算法在城市环境中。的算法提供更好的能量平衡,更有效的转发模式,和更灵活的部署,将有助于为未来铺平道路智能城市dtn网络和不同的应用。在未来进一步的研究仍然是必要的;我们应该寻找更高效的回报函数性能优化和进一步实验使用真实的数据集。此外,应该有一个高效节能的睡眠和觉醒机制在城市环境中。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

作者要感谢人审查和提供一些宝贵的意见,提高论文质量。这项工作还支持中国自然科学基金(61272448和61272448号),中国教育部博士基金(没有。四川20110181130007)、科技支持计划(2012号。2011 rz0004 gz0005, 2015 jy0047),科技部门和软科学基金四川(号2014 zr0146和14 ycg052)。

引用

1. t . Watteyne和k . s . j .高压球阀“智慧城市通过基于标准的无线传感器网络,”IBM杂志》上的研究和发展卷,55 7:1-7:10,2011页。视图:出版商的网站|谷歌学术搜索
2. c .京l . Ren, d .顾“地理路由路灯监控系统的基础上”程序的计算机设计和应用程序(ICCDA”国际会议10)页V3235-V3238 IEEE,秦皇岛,中国,2010年6月。视图:出版商的网站|谷歌学术搜索
3. g . Cardone p·贝拉,a .使得科拉迪,l . Foschini”有效的合作监控智能城市:收敛马奈和传感器网络的快速数据收集,”第四ITU万花筒学报》学术会议:完全网络化的人类未来网络创新和服务(K”11)2011年12月,页1 - 8,。视图:谷歌学术搜索
4. h . Chourabi t, s·沃克et al .,“理解智能城市:一个综合框架,”45夏威夷国际会议系统科学学报》(HICSS 12)2012年1月,页2289 - 2297。视图:出版商的网站|谷歌学术搜索
5. f . d . Wang, b,, y,, z,“分析沟通能力vessel-based海洋监测延迟容忍网络”车间IEEE无线通信和网络研讨会论文集(WCNCW 13)IEEE,页200 - 204年,2013年4月。视图:出版商的网站|谷歌学术搜索
6. j .怀亚特伯利,r·琼斯l . Torgerson和s . Wissler”网络中断宽容NASA EPOXI任务飞行验证实验”学报第一国际会议上卫星和空间通信的进步(SPACOMM ' 09)IEEE,页187 - 196年,2009年7月。视图:出版商的网站|谷歌学术搜索
7. z Lu和j .粉丝,“延迟/容错网络及其在军事通信中的应用,”程序的计算机设计和应用程序(ICCDA”国际会议10),页版本5 - 231 - v5 - 234,秦皇岛,中国,2010年6月。视图:出版商的网站|谷歌学术搜索
8. X.-W。周,Z.-M。程,y叮,J.-G。Lim,刘问:“基于知识动态DTN路由策略,”无线个人通信,卷71,不。3、1819 - 1836年,2013页。视图:出版商的网站|谷歌学术搜索
9. l . Sundararaj和p . Vellaiyan延迟容忍网络路由博弈论问题概述,“国际计算机网络杂志》上,卷2,不。3、152 - 172年,2010页。视图:谷歌学术搜索
10. H.-Y。施,w l。王,N.-M。郭,S.-Y。陈,“博弈论为无线传感器网络:一项调查,“传感器,12卷,不。7,9055 - 9097年,2012页。视图:出版商的网站|谷歌学术搜索
11. r . Machado和s . A . Tekinay”的调查对策论方法在无线传感器网络中,“计算机网络,52卷,不。16,3047 - 3061年,2008页。视图:出版商的网站|谷歌学术搜索
12. r . El-Azouzi h . b . Sidi j . Rojas-Mora和a . p . Azad“延迟容忍网络部分重叠网络:非合作博弈的方法,”Bioinspired模型的网络,信息,和计算系统39卷课堂讲稿的计算机科学研究所、社会信息和通信工程施普林格,页195 - 202年,柏林,德国,2010年。视图:出版商的网站|谷歌学术搜索
13. m . r . Schurgot c Comaniciu, k . Jaffres-Runser“超越传统DTN路由:社交网络的机会交流,“IEEE通讯杂志,50卷,不。7,155 - 162年,2012页。视图:出版商的网站|谷歌学术搜索
14. 美国Bharathi、d·肯普和m . Salek“竞争影响社交网络,最大化”互联网和网络经济卷,4858在计算机科学的课堂讲稿施普林格,页306 - 311年,柏林,德国,2007年。视图:出版商的网站|谷歌学术搜索
15. f·w·z . Li林,和y . Wang, j·l·周”DTN路由与固定站在城市环境中基于地理网格的方法,”无线个人通信,2015年。视图:出版商的网站|谷歌学术搜索
16. T.-M。范教授和美国Fdida DTN支持新闻传播在市区,“计算机网络卷,56号9日,第2291 - 2276页,2012年。视图:出版商的网站|谷歌学术搜索
17. 郭y, s Schildt、t . Pogel和l .狼”检测恶意行为在公共交通车辆DTN,”全球信息基础设施研讨会(GIIS 13)2013年10月,页1 - 8,。视图:出版商的网站|谷歌学术搜索
18. 答:Keranen f·埃克曼,j . Karvo和j·奥特,“工作日运动模型,”学报第一ACM SIGMOBILE研讨会流动模型页,33-40 ACM, 2008年。视图:谷歌学术搜索
19. 答:Keranen、j·奥特和t . Karkkainen“DTN协议评估一个模拟器,”第二届国际会议上仿真工具和技术,55页,ICST(计算机科学研究所Social-Informatics和电信工程),2009年。视图:谷歌学术搜索

版权

版权©2015文藻李等。这是一个开放分布式下文章知识共享归属许可,它允许无限制的使用、分配和复制在任何媒介,提供最初的工作是正确引用。