计算机系统应用  2018, Vol. 27 Issue (1): 212-218   PDF    
引用本文
张云, 郑啸, 黄溯. 基于虚拟积分激励的内容部署方法. 计算机系统应用, 2018, 27(1): 212-218.http://www.c-s-a.org.cn/1003-3254/6144.html   
Zhang Y, Zheng X, Huang S. Content Deployment Method Based on Virtual Credit. Computer Systems and Applications, 2018, 27(1): 212-218(in Chinese).http://www.c-s-a.org.cn/1003-3254/6144.html   
基于虚拟积分激励的内容部署方法
张云1, 郑啸1, 黄溯2     
1. 安徽工业大学 计算机科学与技术学院, 马鞍山 243000;
2. 安徽马钢自动化信息技术有限公司, 马鞍山 243000
收稿日期：2017-03-28; 修改日期：2017-04-20; 采用时间：2017-05-02; csa 在线出版时间：2017-12-22
基金项目：国家自然科学基金(61402009); 安徽省科技重大专项(6030901060); 安徽省高校自然科学研究重大项目(KJ2014ZD05); 安徽省高校优秀青年人才支持计划
摘要：移动自组织网络是个多跳无线网络, 依靠节点间的合作和转发增强网络的性能, 若将内容部署在网络中适合的位置可以极大地减少节点获取数据的成本, 提高网络的性能. 由于节点是理性的, 在没有利益驱动的情况下, 节点难以与其他节点合作进行内容部署. 本文将虚拟积分激励的方法用于此类内容部署问题中, 激励节点相互合作进行内容部署工作, 从而提高网络性能和降低网络成本. 实验结果表明, 本文的激励方法可以有效地减少内容部署成本.
关键词: 内容部署    激励机制    虚拟积分    
Content Deployment Method Based on Virtual Credit
ZHANG Yun1, ZHENG Xiao1, HUANG Su2     
1. School of Computer Science and Technology, Anhui University of Technology, Maanshan 243000, China;
2. Anhui Ma steel Automation Information Technology Co. Ltd., Maanshan 243000, China
Abstract: The mobile ad hoc network is a multi-hop wireless network, which relies on the cooperation and retransmission between nodes to enhance the performance of networks. If the content is deployed in the appropriate location in the network, it will reduce the nodes’ cost to get the data, and improve the performance of the network greatly. Since nodes are rational, they do not want to work with others on content deployment if there is no profit. In our work, an incentive method based on virtual credit is used in content deployment to encourage the cooperation among nodes on content deployment, then the performance of networks can be improved and the cost can be reduced. The experimental results show that the incentive method can reduce the content deployment cost effectively.
Key words: content deployment     incentive mechanism     virtual credit    

移动自组织网络中, 节点间的通信总是依赖于其他节点转发到达目的地, 若将内容部署在网络中适合位置的节点上, 则可以很大程度上增强网络性能, 提高服务效率[1]. 现实中节点都是理性的, 一般情况下难以与其他节点分享自身资源或耗费自身资源去进行内容部署[2]. 在这种情形下, 如果没有一种激励方式去鼓励节点间的合作, 节点是不愿意与其他节点合作进行内容部署的, 即节点的自私特性. 这些自私节点却依靠其他合作节点来转发自己的数据. 节点的自私行为导致网络性能下降, 也可能导致多跳网络通信失败[3,4]. 为了增强网络性能, 提高服务效率, 降低内容部署成本, 有必要通过激励方法鼓励节点合作, 降低节点的自私性.

本文使用了一种有效的激励方式去鼓励节点合作. 首先, 介绍了内容部署和激励机制的相关技术; 其次, 阐述了基于虚拟积分激励机制的内容部署; 最后, 通过仿真实验表明本文方法的优越性.

1 相关工作 1.1 内容部署

在网络中将内容部署在合适的节点上, 可以增加网络的灵活性, 提高应用的响应时间, 改善网络的拥塞问题[1,5]. 目前, 解决内容部署问题的主要是分布式的方法. Pandit[6]则使用了分布式算法, 在复杂度为O(logn)的情形下解决了Jain等人[7]提出相同复杂度的原始-对偶方法. Oikonomou等人[8]将邻居跳迁移部署应用于一个或者更多的内容部署中, 可以解决分布式和低复杂度k-中值问题的近似解, 且k>1. Smaragdakis等人[9]就利用r-跳转迁移部署策略有效地解决了内容部署问题, 初始服务内容可以根据当前网络的情形自适应的迁移到最佳位置, 并且根据当前需求尽可能地减少进行内容部署的开销, 它可以增加或减少服务内容的数量. Stavrakakis等人[10]通过分布式的方法用一种新的启发式方法解决内容位置的优化问题.

本文考虑的是r-跳转迁移部署策略无容量限制的内容部署问题, 主要解决内容部署中的位置UKM (uncapacitated k-median)和数量UFL(uncapacitated facility location)两个问题[9,11].

UKM问题: 解决网络中部署内容的节点的位置问题, 尽量减少访问用户与能提供服务的节点之间的距离, 将内容部署在网络中的最佳位置节点上.

UFL问题: 解决网络中进行内容部署的节点的数量问题, 在网络中内容部署在过多的节点上虽然可以提高网络性能, 但容易造成资源浪费, 如果将内容部署在过少的节点上又容易造成服务质量的降低, 所以适当地部署内容节点的数量对网络的性能及成本有直接的影响.

令 $G = (V,E)$ 定义为一个网络, $V = \left\{ {{v_1},{v_2},...,{v_n}} \right\}$ 表示为节点集, E表示为无向边. $F \subseteq V$ 表示服务节点集.

定义1. UKM. 服务成本 $C(V,s,k)$ :

$C(V,s,k) = \sum\nolimits_{\forall {v_j} \in V} {s({v_j})} d({v_j},m(v{}_j))$ (1)

式(1)中 $d = ({v_j},m({v_j}))$ 表示节点vj到节点 $m({v_j})$ 的最短路径, $s({v_j})$ 表示用户从节点vj处的服务需求. $m({v_j}) \in F$ 是离节点vj比较近的服务节点. 给定节点集V和距离函数d, 以及服务需求 $s({v_j})$ , $\forall {v_j} \in V$ 选择k个节点作为服务节点最小化.

定义2. UFL. 联合成本 $C(V,s,f)$ :

$C(V,s,f) = \sum\nolimits_{\forall {v_i} \in F} {f({v_i}) + \sum\nolimits_{\forall {v_j} \in V} {s({v_j})d({v_j},m({v_j}))} } $ (2)

式(2)中 $f({v_j})$ 为节点vj的服务成本.

1.2 常用的激励机制

对于内容部署的研究前提假设节点是合作的, 但这在现实中节点是理性的, 为了降低自私节点对内容部署过程的影响, 本文在内容部署过程中引入了激励方法. 当下对激励机制的研究主要分为四类: 基于博弈论激励[12]、虚拟积分激励[13]、社交关系激励[14]以及混合激励[15]. 这些激励方式都满足参与者的某些需求而达到激励的效果.

基于虚拟积分的激励方法是用户通过参与网络中的任务而获得虚拟积分(即一种假想的奖励, 货币等), 当行动和奖励不同步时, 虚拟积分可以很好地调动用户的积极性, 特别在多跳无线网络中的包转发情形中, 虚拟积分也可以用于换取其他奖励.

Chuang等人[16]用虚拟积分补偿来自其他节点的数据转发所消耗的资源. 而所获取的虚拟积分可以用于转发自己的数据, 补偿给帮忙转发的中间节点, 激励它们帮忙转发. 而不合作的节点则不允许使用网络, 不会获得虚拟积分. Zhong等人[17]使用虚拟积分来解决移动自组织网络中自私节点的路由问题. 在该方法中, 发送方如果要发送数据, 则必须使用一定的虚拟积分, 以替代中间节点帮忙转发的成本. Buttyán等人[18]介绍了一个称为nuglet的虚拟货币, 为了激励节点合作而运用到移动自组织网络中.

2 加入激励机制的内容部署分析

本文在研究移动自组织环境下的内容部署基础上融入了虚拟积分的激励方法, 该情形下的内容部署是基于设备选址问题又不同于传统的设备选址问题, 文中的内容是部署在网络中合适的节点上. 本文通过节点的度的值来反映节点与网络中其他节点合作的可能性.

2.1 基于虚拟积分的激励机制

因为节点是理性的, 本文将节点分为两种状态: 空闲状态和忙碌状态. 在进行内容部署之前需要对节点进行访问, 当节点在空闲状态的时候可以直接进行服务部署, 但当节点为忙碌状态的时候, 需要判断节点是否愿意配合网络进行内容部署.

基于激励方法的内容部署研究的主要目标是在网络环境下激励用户节点积极参与内容部署活动, 增强网络性能, 提高用户使用效率. 激励机制可以用以下模型表示:

$I:M - > MIN(C(V,s,k))$ (3)

内容部署激励机制(Incentive, I), 即通过某种激励方式(Mechanism, M)在节点集(V)中确定的服务内容数量(k), 并结合服务需求(s)达到节点在进行内容部署时所消耗的服务费用成本(C)最低.

激励机制还可以用以下模型表示:

$I:M - > MIN(C(V,s,f))$ (4)

内容部署激励机制(Incentive, I), 即通过某种激励方式(Mechanism, M)在节点集(V)中确定服务内容数量(k), 并结合服务需求(s)以及服务成本(f)达到节点在进行内容部署时所消耗的服务费用成本(C)最低.

在该情形中, 节点具有自私性, 但是当网络给予节点一些虚拟积分用于弥补节点在进行内容部署时的资源消耗, 节点可以从忙碌状态转移到空闲状态, 然后进行内容部署. 本文节点所获得的虚拟积分收益可用于后期获取网络资源, 节点的虚拟积分值越大, 享有的获取资源的优先级就越大, 可以优先于其他节点获取资源, 若节点的虚拟积分值为0, 则网络就隔离该节点, 即不提供任何资源给该节点. 网络可以通过激励函数计算给予节点vi的虚拟积分值, 激励函数 $g({v_i})$ 为:

$g({v_i}) = \frac{{r({v_i})}}{{\sum\nolimits_{i = 0} {r({v_i})} }}c({v_i})$ (5)

式(5)中 $c({v_i})$ 为成本函数, 即在节点进行内容部署的花费成本, 在UKM和UFL两种不同情形下, 分别由式(6)或式(7)计算可得. $r({v_i})$ 表示在该节点被访问的次数, 初始值为0, 用于计数, 在 $\Delta t(0 \le \Delta t \le 20)$ 时间内, 该节点每被访问一次r+1, 在 $\Delta t$ 之后, 对r值最大的节点给予激励进行内容部署.

$C({v_j}) = s({v_j})d({v_j},m(v{}_j))$ (6)
$C({v_j}) = f({v_j}) + s({v_j})d({v_j},m(v{}_j))$ (7)

上式中 $m({v_j}) \in F$ 是离节点vj比较近的服务节点. 服务成本函数可由式(8)表示:

$f({v_j}) = w{({v_j})^{1 + {\partial _G}}}$ (8)

上式中 $w({v_j})$ 是节点 ${v_j} \in V$ 的度, 节点的度为该节点与系统中其他节点的连通度之和, 反映了节点与系统中其他节点间协作的可能性. ${\partial _G}$ 是图G的度的偏度值, ${\partial _G}$ 服从Hill估计可由式(9)和式(10)计算得:

$\hat \alpha _{k,m}^{(Hill)} = 1/{\hat \gamma _{k,m}}$ (9)
${\hat \gamma _{k,m}} = \frac{1}{k}\sum\nolimits_{i = 1}^k {\log \frac{{{X_{(i)}}}}{{{X_{(k + 1)}}}}} $ (10)

上式中 ${X_{(i)}}$ 表示在样本 ${X_1},{X_2},...,{X_n}$ 中第i大的值.

由于资源有限, 节点会根据当前损失的利益大小判断是否接受网络提供的激励值, 进而决定是否从忙碌状态转换到空闲状态, 若当前的节点状态满足式(11), 则节点接受当前的激励值, 允许进行内容部署:

$\sum\limits_{j = 0} {{\lambda _{{v_j}}}} \le p(\sum\limits_{i = 0} {{\lambda _{{v_i}}}} + \sum\limits_{j = 0} {{\lambda _{{v_j}}}} )$ (11)

上式中节点vi和节点vj分别表示用户节点和服务节点, $\lambda $ 作为节点的标识位, 用于该节点的数据获取次数的记录, p是概率值. 通过式(11)计算 $\Delta t$ 时间内该节点的数据获取次数与网络中所有节点的数据获取次数的关系, 判断当前节点在网络中的数据获取情况, 节点依据数据获取情况决定是否接受网络提供的激励值, 并通过实验对参数p进行调整.

2.2 算法描述

本节根据内容部署模型及分析, 给出算法描述.

(1)激励算法

本文给出激励算法, 计算节点获取的虚拟积分值, 在 $\Delta t$ 时间内, 分别记录所有节点被访问的次数, 选取数值最大的节点并判断是否满足部署条件, 若满足, 则计算给予该节点的虚拟积分值, 虚拟积分值越大的节点, 在网络中获取资源的优先级就越高. 正是由于这些节点接受激励进行内容的部署, 从而减少了网络查找空闲节点和计算适合服务节点位置所造成的资源和时间的浪费, 有效地减少了部署成本, 算法描述如算法1.


(2)服务节点确定算法

在服务节点确定过程中, 所有节点随机分布在网络中, 本文先随机选取k个节点作为初始服务器节点, 再用k-median算法确定该k个服务器节点的位置. 在确定服务器节点的位置过程中, 用弗洛伊德算法找到节点vi到服务器节点vj的最短路径dij, 用于计算进行内容部署的成本, 选取成本较低的节点作为服务器节点.

SiteInfo表示所有节点信息; ServerInfo表示所有服务节点信息; ServerSize表示服务节点数量; SiteSize表示节点数量; iterMax表示k-median算法的最大迭代次数; t表示时间间隔. 根据网络当前的环境信息用弗洛伊德算法计算距离矩阵和路径, 并确定服务节点的位置, 算法如算法2.


(3)服务节点个数确定算法

在UFL情形下, 不仅可以确定服务节点的位置, 同时也可以确定服务节点的个数. 在部署服务内容过程中, 由于考虑了服务成本, 过少的部署内容会达不到增强网络性能和提高服务效率的作用; 过多的部署内容就会造成部署成本的浪费, 增大了服务部署开销. 确定合适的服务节点个数对增强网络的性能、提高服务效率、降低部署成本都产生了很大的影响. 在部署内容初期, 部署内容的成本随着服务节点个数的增加而减少, 但是到达一个值时, 部署成本就会随着服务节点个数的增加而增加.

ServerSize表示服务节点最大数量; iterMax表示最大迭代次数; radius表示r跳值, b[n]存储服务节点, 本文取r=1, 表示距离节点1-跳的用户节点. 算法如算法3.


3 实验仿真分析 3.1 实验环境与参数设置

为了验证添加本文的激励方法对网络的有效影响, 本文分别对节点是无私的、节点是自私的以及加入激励方法的情形做了对比实验. 实验环境为Windows 7操作系统, 使用matlab 2010b编写算法进行仿真实验.

本文的方法在E-R(Erdős-Rényi)随机图中进行实验仿真, E-R随机图中两个节点之间存在一条边的概率p=0.5[19]. 节点在网络中移动的速度大小为1 m/s、方向随机. 节点规模分别为100、200、300和400, 最大迭代次数为200代. UKM中的服务节点个数为5个, UFL中的服务节点个数根据迭代优化最终确定.

3.2 实验结果

在E-R图中, 本文分别就UFL和UKM情形下对网络节点数, $\Delta t$ , 服务站点数进行了实验比较, 图1 为UFL情形下 $\Delta t$ 对激励方法的影响, 图2为UFL情形下节点规模对激励方法的影响, 图3为服务节点个数对激励方法影响, 图4为UKM情形下 $\Delta t$ 对激励机制的影响, 图5为UKM情形下节点规模对激励机制的影响, 图6和图7为本文实验结果与Georgios实验结果对比.

图 1 UFL情形下 $\Delta t$ 对激励方法的影响(节点个数n=200)

图 2 UFL情形下节点规模对激励方法的影响( $\Delta t$ =10)

如图1, 在UFL情形下, 节点规模为200, 分别对 $\Delta t$ =5、10、15和20几种情形进行了实验对比, 从上述实验结果对比图可知, 当 $\Delta t$ =10时, 激励机制对网络的影响效果优于当 $\Delta t$ =5、15和20时的情形.

如图2, 在UFL的情形下, 通过上述不同节点数之间的实验对比我们可以发现, 无论节点规模是100, 200, 300或400, 它对于本文提出的激励方法是没有影响的, 本文提出的方法依旧能有效地减少网络成本.

如图3, 在UFL情形下, 节点规模为300. 通过上述实验结果可以看出, 部署内容所需成本随着服务节点个数增加而减少, 但是, 当网络所需成本减少到一定程度时, 就会随着服务节点个数增加而增加.

图 3 服务节点个数对激励方法影响

如图4, 在UKM情形下, 节点规模为200, 分别对 $\Delta t$ =5、10、15和20几种情形进行了实验对比, . 从上述实验结果对比图可知, 当 $\Delta t$ =10时, 激励机制对网络的影响效果优于当 $\Delta t$ =5、15和20时的情形.

图 4 UKM情形下 $\Delta t$ 对激励机制的影响(节点个数n=200)

如图5, 在UKM的情形下, 通过上述不同节点数之间的实验对比我们可以发现, 无论节点规模是100, 200, 300或400, 它对于本文提出的激励机制方法是没有影响的, 本文提出的方法依旧能有效地减少网络成本.

图 5 UKM情形下节点规模对激励机制的影响( $\Delta t$ =10)

如图6, 本文实验中UFL情形下部署成本与文献[9]中结果对比, 通过上述实验对比我们可以发现, 本文的激励机制方法在减少网络成本方面具有一定效果.

图 6 与Georgios实验结果对比

如图7, 在UKM情形下, 本文的部署成本与集中式的UKM成本比率与文献[9]中的结果对比, 我们可以发现, 在UKM情形下, 本文的激励机制方法能有效地减少网络成本.

图 7 与Georgios实验结果对比

4 结语

本文描述了一种激励方法, 并将其应用于移动自组织网络环境下的内容部署问题中. 文中分别就节点是无私的, 自私的以及带有激励方法的情形下进行了仿真实验对比, 有效地验证了加入激励方法后对网络的性能有了明显的提高. 本文存在的不足之处: 虽然本文验证了基于虚拟积分的激励方法在E-R随机图中的有效性, 但不确定对其他网络模型是否有效; 在考虑节点自私的情形时, 没有考虑节点的转发能耗等问题. 针对这些问题, 还需要对基于激励方法的内容部署进行更加深入的研究.

参考文献
[1]
尹浩, 袁小群, 林闯, 等. 内容网络服务节点部署理论综述. 计算机学报, 2010, 33(9): 1611-1620.
[2]
Ciobanu RI, Dobre C, Dascalu M, et al. Collaborative selfish node detection with an incentive mechanism for oppor-tunistic networks. Proceedings of 2013 IFIP/IEEE International Symposium on Integrated Network Management. Ghent, Belgium. 2013. 1161–1166.
[3]
Marti S, Giuli TJ, Lai K, et al. Mitigating routing mis-behavior in mobile ad hoc networks. Proceedings of International Conference on Mobile Computing and Networking. Boston, MA, USA. 2000. 255–265.
[4]
Michiardi P, Molva R. Simulation-based analysis of security exposures in mobile ad hoc networks. Proceedings of European Wireless Conference. Florence, Italy. 2002. 15–17.
[5]
脱立恒, 倪宏, 李满天, 等. 覆盖网络中多服务静态部署算法. 西安电子科技大学学报(自然科学版), 2014, 41(4): 137-143.
[6]
Pandit S, Pemmaraju S. Return of the primal-dual: Distri-buted metric facilitylocation. Proceedings of the 28th ACM Symposium on Principles of Distributed Computing. Calgary, AB, Canada. 2009. 180–189.
[7]
Jain K, Vazirani VV. Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation. Journal of the ACM, 2001, 48(2): 274-296. DOI:10.1145/375827.375845
[8]
Oikonomou K, Stavrakakis I. Scalable service migration in autonomic network environments. IEEE Journal on Selected Areas in Communications, 2010, 28(1): 84-94. DOI:10.1109/JSAC.2010.100109
[9]
Smaragdakis G, Laoutaris N, Oikonomou K, et al. Distributed server migration for scalable internet service deployment. IEEE/ACM Transactions on Networking, 2014, 22(3): 917-930. DOI:10.1109/TNET.2013.2270440
[10]
Stavrakakis I. Some distributed approaches to the service facility location problem in dynamic and complex networks. Thai M, Pardalos P. Handbook of Optimization in Complex Networks. New York. Springer. 2012. 405–432.
[11]
Pantazopoulos P, Karaliopoulos M, Stavrakakis I. Distributed placement of autonomic Internet services. IEEE Transactions on Parallel & Distributed Systems, 2014, 25(7): 1702-1712.
[12]
曲大鹏, 王兴伟, 黄敏. 移动对等网络中自私节点的检测和激励机制. 软件学报, 2013, 24(4): 887-899.
[13]
Charilas DE, Georgilakis KD, Panagopoulos AD. ICARUS: Hybrid incentive mechanism for cooperation stimulation in ad hoc networks. Ad Hoc Networks, 2012, 10(6): 976-989. DOI:10.1016/j.adhoc.2011.12.010
[14]
吴垚, 曾菊儒, 彭辉, 等. 群智感知激励机制研究综述. 软件学报, 2016, 27(8): 2025-2047. DOI:10.13328/j.cnki.jos.005049
[15]
陈国利. 基于激励的机会网络协作传输机制[硕士学位论文]. 北京: 北京邮电大学, 2015.
[16]
Chuang MC. An incentive-based mechanism for fair bidirectional transmissions in wireless mesh networks. Computers & Electrical Engineering, 2015(41): 342-356.
[17]
Zhong S, Chen J, Yang YR. Sprite: A simple, cheat-proof, credit-based system for mobile ad-hoc networks. Proceedings of the 22th Annual Joint Conference of the IEEE Computer and Communications. San Francisco, CA, USA. 2003. 1987–1997.
[18]
Buttyán L, Hubaux JP. Enforcing service availability in mobile ad-hoc WANs. Proceedings of 2000 the 1st Annual Workshop on Mobile and Ad Hoc Networking and Computing. Boston, MA, USA. 2000. 87–96.
[19]
Erdös P, Rényi A. On random graphs I. Publicationes Mathematicae, 1959(6): 290-297.