基于效用的机会网络物-物交换激励机制-姚建盛.pdf

《基于效用的机会网络物-物交换激励机制-姚建盛.pdf》由会员分享，可在线阅读，更多相关《基于效用的机会网络物-物交换激励机制-姚建盛.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2016年9月 Journal on Communications September 2016 2016182-1 第37卷第9期 通 信 学 报 Vol.37 No.9基于效用的机会网络“物物交换”激励机制 姚建盛1,2，马春光1，袁琪1 (1. 哈尔滨工程大学计算机科学与技术学院，黑龙江 哈尔滨 150001；2. 吉林师范大学计算机学院，吉林 四平 136000) 摘 要：针对机会网络环境下简单“物物交换”（SBT, simple barter trade）激励机制因盲目缓存而降低网络性能的问题，设计一种基于效用的“物物交换”（UBT, utility-based barter tra

2、de）激励机制。UBT通过预测未来相遇节点和相遇节点转发消息到目的节点的概率进行缓存决策从而提高了缓存效率和网络性能。仿真实验证明，和SBT相比，UBT在有效激励节点协作的同时能用更少的网络负载获得更高的投递率和更低的时延。 关键词：机会网络；自私；“物物交换”激励机制；效用 中图分类号：TP393 文献标识码：A Utility-based barter trade incentive scheme in opportunistic network YAO Jian-sheng1,2, MA Chun-guang1, YUAN Qi1(1. College of Computer Scien

3、ce and Technology, Harbin Engineering University, Harbin 150001, China; 2. College of Computer Science, Jilin Normal University, Siping 136000, China) Abstract: In opportunistic networks, existing simple barter trade (SBT) incentive scheme degraded the network per-formance due to the blindly caching

4、 strategy. So a utility-based barter trade (UBT) incentive mechanism was proposed. In the UBT scheme, nodes cache messages by predicting their future encounters and the probability that the encounters for-ward these messages to their destinations, which improved the caching efficiency and the networ

5、k performance. Simu-lated results show that, compared with SBT, UBT can obtain higher delivery ratio and lower delay by less network cost and effectively motivate nodes cooperation as well. Key words: opportunistic networks, selfishness, barter trade incentive mechanisms, utility 1 引言 机会网络1,2利用节点移动带

6、来的接触机会实现不存在完整通信链路的节点间通信，这使手持便携设备和车载设备等可以随时随地感知并扩散热点区域信息，满足物联网泛在互联与透彻感知的需求3，对IoT和普适计算有重要意义。 机会网络之所以能实现间歇性连接网络的通信，在于采用“存储携带转发”的路由模型，这显然需要节点间的协作。然而，在实际机会网络系统中，节点为了节省资源或安全等原因往往不愿意为其他节点缓存、携带并转发数据，这种自私行为严重影g2721了机会网络性能4。 g19036对自私g19394g20076，g1268统g9620g2181机g2058g1039要有g3534于reputation的g9620g2181机g20585

7、和g3534于credit的g9620g2181机g20586，然而机会通信为设计这g1135g9620g2181机g2058带来g5468g3835g6373g6124。在g3534于 reputation 的g9620g2181机g2058中，g11429g8991g991g980g17351节点的转发行这g980g1863g19202g19394g20076在间歇性链接的机会网络中g17751g19602实现。在g3534于 credit 的g9620g2181机g2058中，通g5132需要可信g12544g989g7053或g10317g8542g11840g1226g1457g19

8、568g11017g4388g17147g5077的可信，并需要g16311g1927g2533g16853g6915g1196和g6915g1196g3822g4581的g19394g20076，这在g6311g6181g20652g5242动g5589的g2010g5079g5347机会网络中g1075g5468g19602实现。 以g9902种g9620g2181机g2058g18129g4570g991g980g17351节点的转发行为g5415作g7393g2165，g3698g2164了在机会网络g10627g3671g991的设计g19602g5242。g11468g8616之g

9、991，BUTTYN7设计的g3534于barter的g9620g2181机g2058，g7424g7003g12628g12228为g12628g2345“物物g1144g6454”g708SBT，simple 收稿日期：2016-04-06；修回日期：2016-06-17 基金项目：国家自然科学基金资助项目（No.61472097）；高等学校博士学科点专项科研基金资助项目（博导类）（No.20132304110017）Foundation Items: The National Natural Science Foundation of China (No.61472097), Educa

10、tion Ministry Doctoral ResearchFoundation of China (No.20132304110017) doi:10.11959/j.issn.1000-436x.2016182 万方数据第9期 姚建盛等：基于效用的机会网络“物物交换”激励机制 103 barter tradeg709g9620g2181机g2058，g16825g9620g2181机g2058g12628g2345、有g6940、g7143于实现。g1306SBT在g9620g2181节点g5122g2173其他节点缓存g9052息时并g7422g13783g15397g7422来会和g

11、16853g11468g17947以g2462g11468g17947节点的需求，这会g4560g14280不g5529要的缓存而g19489g1314网络性能。g3926节点u缓存g9052息mg2530，在以节点u为g17227点、转发g9052息m的路g5464g990，所有节点g18129不能g6116g2163g6249g17894mg2052其g11458的节点，g18039g1052缓存m不g1177g9022g17165了带g4497和存储资源，而g1000会因g19471g11873缓存g2524适g9052息而g19489g1314网络性能。 g3534于g6940用的缓存

12、能有g6940g6564g20652节点缓存g6940g105878，为g8504，g7424g7003g19036对机会网络设计g980种g3534于g6940用的“物物g1144g6454”g708UBT，utility-based barter tradeg709g9620g2181机g2058。然而，在机会网络g10627g3671g991设计g2524适的缓存g6940用并计算其g1552g5468有g6373g6124。g20330g1820通g17819g20056g8991g7422来g11468g17947节点、g11468g17947时g7171g2554能g6116g21

13、63转发g9052息g13485g11468g17947节点以g2462g11468g17947节点g6116g2163g6249g17894g9052息g2052其g11458的节点的g8022g10587设计g20652g6940的缓存g12586g11065，然g2530g13485出g11468g1863g5242量的g20056g8991g7053法，最g2530设计 UBT 机g2058并g2010析其开销。在真实移动轨迹和人工移动轨迹g991的仿真实验表明，UBT不g1177能有g6940g9620g2181节点协作，而g1000和SBTg11468g8616通g17819更小的

14、网络负载达g2052更g20652的g6249g17894g10587和更小的时延。 2 相关工作 g7424节g13485出和g7424g7003g11468g1863的研究工作，包括g9620g2181机g2058和g3534于g6940用的缓存g12586g11065，g9620g2181机g2058g1039要介绍g3534于reputation的g9620g2181机g2058、g3534于credit的g9620g2181机g2058和g3534于barter的g9620g2181机g2058。 在g3534于 reputation 的g9620g2181机g2058中，节点通g1

15、7819g6564供转发g7393g2165g6564g20652自己的信誉，信誉越g20652得g2052其他节点g6564供g7393g2165的机会越g3835。然而间歇性连接为g11429g8991g991g980g17351节点的转发行为带来困g19602。为g8504 PRI9g6564出g6116g2163转发证书g8022念g11429g8991节点转发行为；SENSE10设计g3534于g990g991g7003的自私节点g11429g8991算法；TRSS11利用社会g11468似性管理信任。 在g3534于 credit 的g9620g2181机g2058中，节点通g17

16、819g6564供转发g7393g2165获取虚拟g17147g5077，然g2530用虚拟g17147g5077g6454取其他节点的转发g7393g2165。g3926不g2533外g6564供g7393g2165，自己g1075没有“资金”购买g7393g2165。然而，机会网络的g20652g5242动g5589g6311g6181和随机性路由使源节点g5468g19602g20056知g2533g16853g6915g1196和g6915g1196g3822g4581的g19394g20076。为g8504，NING 等12g6564出g1177g2533最终g6249g17894者

17、g6915g1196酬金的g9620g2181机g2058；MuRIS13通g17819定价和回报函数g9620g2181节点协作；MobiCent14通g17819博弈论和算法机g2058设计g9620g2181g11468容的g6915g1196机g2058；SIS15g6564出g3534于g7393g2165优g1820权的g9620g2181机g2058代替credit机g2058。 国内学者在g4570g1268统g9620g2181机g2058应用于机会网络的研究中g1075做了g3835量工作1619。然而以g990g9620g2181机g2058研究g18129g4570g9

18、91g980g17351节点的转发g5415作g7393g2165，利用某种g5242量g708信誉或虚拟g17147g5077g709衡量节点g6564供g7393g2165的g3822g4581，g1927定其获得g7393g2165的资g7424。这虽然g3698强了g9620g2181机g2058的灵活性，g3926便于g7393g2165的转移或g1268g17894，g1306g1075g3698g2164了在机会网络g10627g3671g991的设计g19602g5242。 g3534于barter的g9620g2181机g2058中，节点g4570g990游节点g6564供的

19、数据g5415作g7393g2165，通g17819以物g6454物的g7053g5347g9620g2181节点g1039动缓存数据，在机会网络中则g8616g17751容g7143实现。g20330g1820，通g17819判断g990游节点数据检g8991其自私行为g8616g17751容g7143，不受链路断开影g2721；其次，不使用虚拟g17147g5077，避免g6915g1196带来的困g19602；最g2530，g1144g7143g1177发生在2个g11468g17947节点之间，使机g2058容g7143g2010g5079g5347实现。g7003献20g4570g1

20、6825机g2058应用于P2P网络；g7003献7g20330次g4570g16825机g2058引入机会网络；LIU等21指出SBT存在g19489g1314网络性能的g19394g20076，并通g17819g3534于社区的“物物g1144g6454”g6564g20652网络性能；LI22g13485出机会网络g10627g3671g991g3534于barterg9620g2181机g2058的研究现状。 g3534于g6940用的缓存g12586g11065在机会网络路由中有g3835量应用，g3926g3534于移动轨迹的g6940用23、g3534于社区的g6940用24、g

21、3534于g11468g17947历史的g6940用25等。g1306g7171现有g7003献g5468g4581有g13783g15397g2052节点管理缓存时丢弃g9052息的因素26，g7424g7003在g7003献26的g3534础g990g13485出更精确的g9052息丢弃g8022g10587g20056g8991g7053法，并设计适g2524g3534于barterg9620g2181机g2058和机会网络的缓存g6940用以g6564g20652网络性能。 3 基于效用的“物物交换”激励机制 为g6564g20652SBT的网络性能，g20330g1820设计g980

22、种g20652g6940的缓存g6940用并g13485出计算g7053法，然g2530设计g3534于g6940用的“物物g1144g6454”g9620g2181机g2058并g2010析机g2058的开销。 3.1 效用值计算 计算g6940用g1552的原则g7171不g1177有利于节点自身利益，而g1000能g6564g20652网络整体性能。节点v为u缓存g9052息m的g6940用取g1927于v和ug7171g2554g11468g17947以g2462g11468g17947时ug7171g2554g2533v请求m，而 ug7171g2554g2533v请求m取g1927

23、于ug7171g2554为m的g11458的节点或者u的g991游节点g7171g2554需要m。 设dg7171g9052息m的g11458的节点，rt g7171g9052息m的剩余生存时间，v g7171节点v的中继节点集，则v缓存g9052息m的g6940用为 1, =()+ (), vmmmvvr wwrwvdUttvd =(1) 2016182-2 万方数据104 通 信 学 报 第37卷 g5415v=d时，v直接缓存m，g2554则g6940用g1552由2部g2010组g6116：g3926果节点v在rt 内直接g6249g17894g9052息mg2052d的g8022g1

24、0587 ()mvrt g17751g3835，则mvU 越g3835，因为 d g980定会请求g9052息m，这样v可以从dg18039里g1144g6454g9052息；g3926果 ()mwrtg17751g20652，则wg2533v请求m的g8022g10587g17751g3835，则mvU g1075越g3835。 g5347(1)中 +1vww=， 和w g7171节点 u ( vuv )直接g6249g17894mg2052其g11458的节点的g8022g10587g1552在g2524g6116g6940用时所占的g8616例，g16825g8616例与节点w和v的g1

25、1468g17947g8022g10587g6116正g8616，其中，1=1+ ( )vvw rwt，()1()vvw rwvw rwtt=+， ()vw rt g7171节点v和w在时间rt内的g11468g17947g8022g10587， () 1vw rt = ，则g5347(1)整g2524g6116g5347(2)。 + + 1, =() (), 1+ ( )vvmvw wmwvvvwwvvdTTUvdT=(2) 其中， ()murt 取g1927于在时间rt 内节点u和dg7171g2554g11468g17947、g11468g17947时dg7171g2554已经缓存m、u

26、g7171g2554还拥有m，由g8504得 () () ( ) ( )mmmur udrd ru rtttttt=+ (3) 其中，tg7171g5415前时刻， ()ud rt g7171节点u和d在rt 内的g11468g17947g8022g10587， ()mdrtt + g7171节点d在rtt+ 时刻之前没有从其他节点缓存m的g8022g10587， ()murtt + g7171节点u在时刻rtt+ 前没有丢弃g9052息m的g8022g10587。 3.2 度量值预测 g7424节g13485出g6940用计算中g11468g1863g5242量g1552的g20056g89

27、91g7053法。 1) 节点对(u, v)在时间t内的g11468g17947g8022g10587 ()uvt ，在不g2528移动模型g991的求g16311g7053法不g2528。g7424g7003g17885g6333g7393从g10432g12447g2528g2010g5079的随机路点移动模型(RWP, random way point)和真实移动轨迹数据集Infocom06，g1563设在这2 个移动模型g991，节点g11468g17947g17819g12255g7393g18129从 Poisson g2010g5079，则 () 1 euvtuvt= ，其中，u

28、v g7171节点对(u, v)的g11468g17947g20069g10587。g991g19766验证在这2个移动模型中节点g11468g17947g17819g12255g7171g2554可用 Poisson g2010g5079g5326模，并g13485出g11468g17947g20069g10587的计算g7053法。 在经g1868g10432g12447g2528g2010g5079移动模型g991，g7003献27已经验证了在节点通信g2334g5464g17840小于移动区域时，节点g11468g17947g17819g12255g7393从 Poisson g201

29、0g5079，并g13485出g11468g17947g20069g10587的计算g7053法，g2375*2E=rVA ，其中，rg7171节点g7092g13459g1268g17767g2334g5464，EV*g7171节点移动g17907g5242的数学g7411g7407，Ag7171节点移动区域，g7171g1393g17194于不g2528移动模型的g5132数，在RWP移动模型g991 =1.368 3。 在真实移动轨迹模型中，g1039g8981g7003献g16760为节点g11468g17947g17819g12255g7393从 Poisson g2010g5079

30、24,26，g1306g7171g1075有研究人g2604g16760为g7393从g5142g10587g2010g50792,3。g991g19766用g11394g4584g178862 g1946则验证Infocom06数据集g17829似g7393从Poissong2010g5079并g13485出g11468g17947g20069g10587计算g7053法。 g4570节点对(u, v)g11468g17947g17819g12255g2010g6116k个区间，统计g8611个区间中g11468g17947次数1n ,2n ,midhorizellipsis ,kn ，g5

31、647g11468g17947次数1kiiN n=，求出g8611个g11468g17947区间的g11468g17947g20069g10587iinN = (i=1,2,midhorizellipsis,k)和节点对的g11468g17947g20069g10587uvkN = 。g1208原g1563设H0g7393从Poissong2010g5079，g2375X P( )，求出随机g2476量Xg14865在g8611个区间的g8022g10587ip (i=1,2,midhorizellipsis,k)。 为了检验原g1563设H0，g2375检验理论g2010g5079和统计g2

32、010g5079g7171g2554g12538g2524，g6238g1571g5058iip 的g2164权g5191g7053和作为理论g2010g5079与统计g2010g5079之间的g5058g5334g524221=( )kii iicp=。其中，ic g7171g2520个区间的权，g1393据g11394g4584g17886g1946则，g3926果取=iiNcp，则g5415N 时，统计量的g2010g5079g17247于自由g5242为 1k 的2 g2010g5079， g7171理论g2010g5079中需要利用样g7424g16278g8991g1552g128

33、4计的g7422知g2454数个数，这里取g1552为 1。经g17819g8991g16809，在显g14891性g8712g5191 =0.05 时，Infocom06数据集中g17241g1781985% 的节点对(u, v)的g11468g17947g17819g12255g7393从g11468g17947g20069g10587为uvkN = 的Poissong2010g5079。 2) 节点d在t时刻之前没有从其他节点缓存m的g8022g10587 ()mdt ，等价于d在t之前没有和任g1321缓存m的节点g11468g17947的g8022g10587，g2375 ( )=

34、(1 ( )(1 ( )mmdzdzzdttt(4) 其中，1()mzt g7171节点在 t 之前缓存 m 的g8022g10587，1()zdt g7171 z 和 d 在 t 之前不g11468g17947的g8022g10587。g5415 t=1时， ()mzt 的g2033g3999g1552为1, (1)=0, mzvmvm不是 的源节点是 的源节点，于g7171能计算 ()mz K 的g1552( =2,3, , 1t midhorizellipsisK )。g5347(4)的计算有2种g7053g7708：g980种g7171g8611个节点计算自己的 ()md ，然g253

35、0在和其他节点g11468g17947时g5456g8504g1861g1151信息，g1306g7171在机2016182-3 万方数据第9期 姚建盛等：基于效用的机会网络“物物交换”激励机制 105 会网络g10627g3671g991g5468g19602g2462时g1144g6454信息，g4560g14280计算不g1946确；g2490g980种g7171由网络g6922集全g4628信息并g17839行集中g5347计算，然g2530g4570计算g13479果和网络节点g1861g1151，g16825g7053法的g20056g8991精g5242g20652，g1306在

36、真实的自组g13467网络中g5468g19602实现，因g8504g2494能g7171理论g2454g13783g1552。 g18504于g5347(4)的计算g3809g7446性g17751g20652，g1000g5468g19602在实际系统中计算其g1552，g13485出g980种适用于实际系统的、g12628g2345的 ()md g1284计g1552，g2375 ()=m rdTTL ttTTL(5) 其中，TTLg7171g9052息m的生存g2620g7411，rt g7171g9052息m生存g2620g7411的剩余时间。g16825g7053法g3534于这样

37、的g16278g4531：g9052息m在网络中g1268g6785时间越g19283，d缓存g2052m的g8022g10587越g3835，g2465之则g8022g10587越小，g16825g7053法的g20056g8991g13479果和集中g5347计算的g5347(4)g5468接g17829，而g1000g16825g7053法计算g12628g2345，g7143于实现。 3) 节点 u 在时刻之前丢弃g9052息 m 的g8022g10587()mu 取g1927于 u 采取的丢弃g12586g11065，g7424g7003g1563定缓存满时节点丢弃g6940用g15

38、52最g1314的g9052息。g1563设 t 时刻节点 v的缓存g5785g1929g3926g3282 1(a)所g12046，缓存中g9052息g6365g6940用g1552从小g2052g3835g6502g5219，g6940用g1552g1314于m的g9052息个数为k，剩余缓存g12366间为 s。g3926g3282 1(b)所g12046，g2052时刻，节点 ug6922g2052s个g9052息g2530缓存满，其中，有i (i=0,1,midhorizellipsis,s)个g9052息的g6940用g1552小于 m，si 个g9052息g6940用g1552g

39、3835于等于m。i 的取g1552g7393从g1120g20045g2010g5079 B(s, p)，g2375 ()P i = Ciisisp q，g8611次g6922g2052g9052息g7171g6502在m前还g7171mg2530的g8022g10587和 m 所在g5415前g1313g13634有g1863，为g12628g2282计算取g5191g3355g5785g1929，g2375p=q=0.5。 图1 节点v的缓存 g5415缓存满g2530，节点 u g1889g6922g2052g7044g9052息时，g6940用g1552最g1314的g9052息g1

40、5999丢弃。g5415g6922g2052g6940用g1552小于m的g9052息时，对丢弃m不g1147生影g2721，g5415g6922g2052g6940用g1552g3835于m的g9052息时，g9052息m会前移，g5415g6922g2052g3822于k+i个g6940用g1552g3835于m的g9052息时，mg15999丢弃。因g8504，g9052息m在时刻之前g15999节点u丢弃的g8022g10587 ()mu g6365g5347(6)计算 12() ( ) ( )mutPtP =(6) 其中，1()P t g7171从时间tg2052节点ug6922g2

41、052s个任意g6940用g1552的g9052息的g8022g10587，g6365g5347(7)计算 001()0()=()( )e!utsPtP tsts=(7)其中，0()ut 表g12046节点 u 在 t g2052g6922g2052任意g6940用g1552的g9052息的g1119g1226数，0 g7171节点ug17947g2052任g1321g980个能g1144g6454g9052息的节点的g20069g10587，为g12628g2282计算，0=uuvv ，ug7171节点u的g20069g13333g11468g17947节点集g2524。 2()P g717

42、1节点 u 从时间g2052g6922g2052g3822于 k+i个g6940用g1552g3835于m的g9052息的g8022g10587，g2375 20()100()=C () )( )e=C 1!muusUiisisuinskiiisi usinPpqPkipqn =+=+(8) 其中， ()muUu 表g12046节点 u 从时刻g2052g6922g2052g6940用g1552g3835于 m 的g9052息的g1119g1226数，u g7171节点 u g17947g2052能g1144g6454g6940用g1552g3835于 m 的节点的g20069g10587，u

43、 g17829似取g1552为0()=umuu mumltUU26， ()ultg7171t时刻u的g9052息g2027表。 3.3 机制设计 在前g19766的g6940用计算中获得节点g11468g17947g20069g10587g7171g1863g19202，3.2 节g13485出在g10432g12447g2528g2010g5079的经g1868移动模型g991节点g11468g17947g20069g10587计算g5347和在真实移动轨迹中的计算g7053法，g7424节g19036对真实移动轨迹g13485出计算节点g11468g17947g20069g10587的g1

44、6826g13466设计。 节点用g3926g3282 2 所g12046的数据g13479g7512g16772g5417并计算和g8611个节点的g11468g17947g20069g10587。数据g13479g7512的g1039体g7171g980个链表L，headg7171g3848指g19036，g8611个链表节点g13512g6264节点u和g980个g11468g17947节点的g11468g17947g20069g10587信息，链表g1815素g7171g13479g7512体id, cf, Qp, next，其中，idg7171和节点ug11468g17947的节点g

45、7643g16794，cfg7171g1120者的g11468g17947g20069g10587，Qpg7171指g2533g1120者g11468g17947g16772g5417g19443g2027Q的指g19036，next指g2533g991g980个节点。cf由Qp指g2533的g19443g2027Q计算，节点g20330g1820g4570时间g12175散g2282，等g2010g6116g14521g5190区间，然g2530g16772g5417g8611个区间内节点g11468g17947次数，g2375g19443g2027Q的g1815素，最g2530g1393据

46、区间数和g11468g17947次数计算cf。 g19443g2027 Q 的设计采用g2494有g4626指g19036的g20046g5219g5502g10627g194432016182-4 万方数据106 通 信 学 报 第37卷 g2027，g7094节省g12366间g2460g7143于g6817作。在实际系统中时间g7171g7092g19492的，节点不可能g16772g5417所有区间的g11468g17947g16772g5417。并g1000真实移动轨迹中节点g11468g17947g1867有g8886动性，g3926节点在g11345g3837g11468g179

47、47g20069g13333，g7214g990则g5468g4581g11468g17947。因g8504为节省存储g12366间并g2465g7156节点g11468g17947的最g7044g17247g2195，引入g9381动g12395g2487的g8022念，g2375节点g2494g16772g5417g5415前W个区间的g11468g17947次数。g5415g19443g2027已满并统计g7044区间时，rear指g19036g3800插入g980条g7044g16772g5417，就会覆盖g980条最老的g16772g5417。 g991g19766g13485出由

48、Q 计算 cf 的g1867体g17819g12255。节点在g8611次g11468g17947时对g11468应g19443g2027Q执行Qrear+；g5415开g3999g7044的统计区间时，更g7044对应的g20069g10587g1552，g1306不需要遍历整个g19443g2027，因为g11468g17947g5647数中g2494g7171g3822了rear指g2533的g1815素，g4581了rearg4570要覆盖的g1815素，其他g1552g18129没g2476，执行代码为：N+= Qrear；rear+；N= Qrear; cf=WN。 在实际系统中，节点g2494需动g5589地为g11468g17947g20069g10587g17751g20652的节点g13512g6264信息，所以L采用链g5347存储。在真实移动轨迹中，与g980个节点g2465g3809g11468g17947的节点集g7171有g19492的、固定的。g3926g32823所g12046，与g980个节点g11468g17947次数g