论文研究-应用Max-Min策略的物联网社区构建方法.pdf

所需积分/C币:9 2019-09-08 15:55:40 614KB .PDF
收藏 收藏
举报

针对如何在面向终端用户的服务网络中实现高效构建代价最小、效用最大的物联网社区的问题,结合物联网的特征,借助The Set-covering理论,提出了一种基于Max-Min的物联网社区构建方法。对问题进行了相关描述,给出了物联网社区的构建方法。理论分析和仿真实验表明,该社区构建方法与CONGA算法相比,具有代价小、效率高的优点。
2462012,48(16) Computer Engineering and Applications计算机工程与应用 各节点信息全部赋值给U,即U={L(v),(v)} 速环境的感知力和有效地传输信息直接影响了整个 步骤3对于算法中每次选取出覆盖区域S的节覆盖区域的高效性。 点集合V赋值给P,P的初始化为④。 33算法效率分析 步骤4当U不为空集时,每次从子区域优先级 CCTA主要思想是通过局部的贪心得到整体的 高的中选择出(ν)最大的节点,将其加入P中;并最优解。在循环体中每次从优先级高的子区域中选 从U中删除直接连接在该节点的所有其他的节点的取最大的影响度Ⅳ(ν)的节点,并将它的直接邻接点放 信息。回到步骒1、步骤2中更新区域优先级和节点入集合P中,直至区域S被覆盖。算法步骤4中对于 影响度的Ⅳ(ν)。循环操作此步骤。 每一轮算法的结東,要重新对各个子区域的优先级 步骤5直至U为空集,表明区域S全部被覆盖。进行排列和节点的影响度的计算,直至U为空为止。 步骤6计算P中节点入度与出度的关系。判断 算法中此算法的性能如下:算法的时间复杂度 是否满足上文给出强弱服务社区定义。若满足,P为为O(min(ⅥS),算法的整体复杂度为O(S 所构建出 Max-Min的物联网服务社区。否则,反min(ⅦS)。这里的S表示区域S被分子区域的 之。算法结東。 个数。 算法步骤2中需要先求出节点影响度Ⅳ(ν),下面 下面将给出CCIA性能的数学证明。 给出节点影响度的算法。设在物联网环境下节点 定理1物联网服务社区构建算法是一次多项式 集合V屮的节点感知数据服从高斯分布从中任取两的时间度的算法 个节点v,F设Y,y是VV的感知的数据,其概率 证明设K(n)=M(max{S:S∈G}。其屮M(m)= 分布函数(pdf为P(x),P(x)。其中y,为一次的∑1,定义M(0)=0。定义P为覆盖区域S的节点集 测量数据。则v,的感知数据置信距离测度为d合,P为最小的节点集合,V为算法步骤4中第次 可表示为: 被选取出的节点。那么先分配给每个子区域一个单 d =erf) 元成本,然后将各个子区域S0中单元成本平分给循 (3)环体中第一次加入P集合中的节点即第一次被覆盖4 d =erf(( 的元素为-(1∪V2…V-。P,为每个节点 的成本价,即 其中ef(O为误差函数,由公式(1)得到0≤d≤1;dn (7) 越小说明V支持V的程度越高。令=1-d,则对 用P表示区域S中总的代价,即 于有x个节点的网络,其关联矩阵R可表示为: P=∑ (8) 那么在最理想的情况下: R P=∑∑P (9) 因为考虑到理想情况下节点覆盖的重复性,所以 但是公式(2)中无法说明每个节点的综合影响 ∑Ps∑∑ (10) 度。下面采用模糊理论中相关性函数确定每个节 S∈py∈S0 点的综合影响度,定义()=n,相关性函数可定 定理2若P∈S,则∑P,≤M(s) ∈S 义为 用与定理1同样的表示方法来证明,若P∈S的 A()-max(B(i, Bglb) (5)任意集合,设1,2,…,,w2表示区域S在V 节点i影响度可表示为 V选取后子区域S中还没有被覆盖的节点, (v1)=min(β(ij)(j=1,2,…,x) (6)所以w,=-1UH20…H,w0=S。那么得到 显然可知,1(v)越大那么节点的影响度就越大,反之1≥v;(w1-w)是对于区域S中第次被覆盖的 就越小 元素。设f是各个子区域中节点全部被覆盖的最小 步骤4中每次从子区域优先级高的中选择出指数即F,F2,…,V。那么有如下公式 I(ν)最大的节点,将其加入P中。这些被选中的节点 就是在当前具有较强的覆盖能力。此类节点具有快 王杨,张林静,严远亭:应用 Max-Min策略的物联网社区构建方法 2012,48(16)247 因为V是贪心算法中循环体中每次选取出的节 0.81 点,它是局部最大限度的覆盖V中的元素,则 0.7 ABCD V-(1Uv2U…∪v=)2≥ 宴0.6 聪0. W-(1∪v2U…∪v-=-1 (12) :0.4 由式(11)和式(12)得到 0.2 0.l P≤∑1w)s∑∑ 各子区域节点的编号 ∑1)=∑(M(m1=)-() 图3节点影响度计算示意图 点影响度是呈上升趋势的。总的来说,两者在某个 M(SD)G≤W-1 数值上会达到影响度的饱和度。 即P-∑M(S)≤M(maxs;S∈G}) (13 因此,本算法的时间复杂度是r(n)=M(max{ 品 S∈G}) 因此,CCTA算法相对于 CONGA算法,其有 高效性、稳定性和目标性。 20 仿真实验与结果分析 邻居节点个数0节点影响度(%) 为了评价本文提出的构建方法的性能,使用 图4节点影响度、邻居距离、节点个数关系 Matlab仿真软件中对CCTA算法进行验证。首先它 实验2节点覆盖度 将描述不同区域的节点影响度,其次从节点重复率 由图5可知:在相同的邻居节点个数时,采用 中和算法运行时间两个方面与 CONGA算法进行比较,CCTA算法的精度要比 CONGA高。首先当邻居节4 从而来体现CCTA算法的高效性。仿真实验如下 点为2时,CCTA的节点影响度为62.85%,而 CONGA 实验1节点的影响度 为90.71%。然后随着邻居节点个数增加,节点的覆 在优先级不同区域中感知节点影响度的计算情盖度也呈上升趋势。但是CCTA在6个邻居节点时 况。由图3可知:不同区域的感知节点数可能是不同已经达到9921%而 CONGA则在10个邻居节点时才 的因此勾个节点的影响度也是不同的。如子区域A,达到99.10%。这就说明CCTA可以采用较少的邻居 B,C中的感知节点影响度是成曲线分布的。本实验节点个数而达到相同的覆盖度。这样也减少了节点 也充分考虑了特殊情况:(1)有的节点是孤立的情况能量的消耗和节点冗余度。 (如子区域C中编号为4的节点),它的节点影响度为 实验3效率比较 0。(2)有的区域只有惟一的节点(如子区域D),那么 实验3中从节点重复率和算法运行时间两个方 它的节点影响度只能是通过与外界其他子区域节点面作比较。本文选取区域中的节点数目从30~150递 间的联系而算出。 增的情况,并实验。由图6可知:(1)节点重复率和运 从图4中可以看出:随着距离的加大,节点影响行时间都是随着节点数目的增加而上升。(2)两种算 度是呈下降趋势;但是随着邻居节点个数的增加,节法在节点数目小于130的情况下,节点重复率是相当 CCTA 90 CONGA 目 CONGA 一 CONGA - CcTA 4 0 2468101214161820 2040 80100120140160 邻居节点个数 节点的数目 图5CCTA与 CONGA与邻居节点个数比较 图6CCTA与 CONGA性能的比较小意图 2482012,48(16) Computer Engineering and Applications计算机工程与应用 的。但是节点数目在130~150.之间,CCIA算法节点 究综述[J北京邮电大学学报,2010,33(3):1-10 重复率是明显小于 CONGA算法。(3)CCTA算法的[2]才华社区挖掘算法研究[D]长春:吉林大学,2008 运行时间随着节点数目的增加,比 CONGA算法上升3]王莉,苏卫华余雪丽一种基于点的多社区谱分解方法门 的幅度也增大。 计算机工程与科学,2009,31(9):8-10. 综上可知:(1)充分考虑不同划分社区的情况 [4]Chvatal Va greedy heuristic for set-covering problem[J] Methematics of Operations Research, 1979, 4(3): 233-235 分类考虑和计算各个子社区的优先级和节点影响 度。(2)考虑节点影响度和邻居节点距离以及邻居节 5 Akkaya K, Younis M. A survey of routing protocols in wireless sensor network[J].Ad Hoc Network, 2005, 3(3): 点个数的关系。(3)相对 CONGA比较,发现CCTA的 325-349 性能有很大的提高 6]何晓东,周栩,干佐,等复杂网络社区挖掘——基于聚类 融合的遗传算法[J自动化学报,2010,36(8):1160-1170 5结论与展望 []刘建书,李人厚,刘云龙,等基于相关性函数和模糊综合 物联网环境下社区的构建要充分考虑物联网节 函数多传感器数据融合门系统工程与电子技术,2006,28 点能量的有限性和动态性,因此木文提出以最小代 (7):1006-1009 价构建物联网社区。本文的方法不仅能动态选取节1向敏,石为人基J数据关联性的无线传感器网络簇内数 据管理方法[]自动化学报,2010,36(9):1343-1350 点、减少节点能量消耗,而且具有较好的效率。下 [9 Newman M E J Fast algorithm for detecting community 步工作将考虑重叠社区的构建问题。 structure in network[J]. Phys Rev E, 2004, 69(2) [10] Radicchi F, Castellano C, Cecconi F, et al. Defining and 参考文献: identifying communities in network[J]. Proc Natk Acad [1]孙其博,刘杰,黎羴,等物联网:概念、架构与关键技术研 Sci,2004,10l(9):2658-2663 (上接219页) Letter,2003,31:308-318. 善ACO算法计算的初始解;邻域搜索范围仍然较小 18 Graham R L, Lawler E L, Lenstra J K, et al. Optimiza 需要扩大:邻城搜索及跳出局部最优解的机制进行 tion and approximation in deterministic sequencing and scheduling: a survey [J].Annals of Discrete Mathematics 进一步研究。 1979,5:287-326 [9] Piehler J, Beitrag E Z Rein lem [j]. Unternehm 参考文献: erforschung, 1960, 4: 138-142 [1] Aldowaisan T, Allahverdi ANew heuristics for no-wait [10] Bagchi T P, Gupta J N D, Sriskandarajah CA review nowshopstominimizemakespanj.computer&Opera of tsp based approaches for flowshop scheduling[j] tions Research, 2003.30: 1219-1230 European Journal of Operational Research, 2006, 169 2 Grabowski J, Pempera J L. Some local search algo- 816-854 rithms for no-wait flow-shop problem with makespan [11] Rock H. The three machine no-wait flowshop problem criterion[J]. Computer Operations Research, 2005,32 is NP-complete[J] Journal of the Association for Com 2197-2212 puting Machinery, 1984, 31: 336-345 [3]潘全科,赵保华,屈玉貴无等待流水车间调度问题的优化[.[12」 Dorico v蚁群优化[M]张军,等译北京:清华大学出版 计算机学报,2008,31(7):1147-154 社,2007 4]NawaκM, Enscore F, Ham LA heuristic algorithm for[13]田岩,谢玉波,周泉,等基于创建解动态控制和局部搜索 the m machine, n job flow shop[J The International 合并的蚁群算法[J系统工程与电子技术,2008,30(1): Journal of Management Sciences, 1983, 11(1): 91-95 160-163 [51 Rajendran C A no-wait flowshop scheduling heuristics [14] Framinan J M, Leisten R, Ruiz-USano R Comparison of to minimize makespan[J]Journal of Operational Re heuristics for flowtime minimization in permutation search Society, 1994, 45: 472-478 flowshops[J]. Computer Operations Research, 2005 [6] Framinan J M, Marcelos s N Evaluating the perfor 32:1237-1254. mance for makespan minimization in no- wait flowshop[15]周泓,李政道,吴学静.一种求解变速机调度问题的混合 sequencing[J]Journal of Materials Processing Technolo- 蚁群优化算法门计算机集成制造系统,208,14(9 gy,2008,197:1-9 1733-1741 [7] Schuster c j, Framinan J M. Approximative procedures[16]王凌智能优化算法及其应用[M北京:清华大学出版社, for no-wait job shop scheduling].Operations Research 2001

...展开详情
试读 5P 论文研究-应用Max-Min策略的物联网社区构建方法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38744153 你的留言是对我莫大的支持
    2019-09-08
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-应用Max-Min策略的物联网社区构建方法.pdf 9积分/C币 立即下载
    1/5
    论文研究-应用Max-Min策略的物联网社区构建方法.pdf第1页
    论文研究-应用Max-Min策略的物联网社区构建方法.pdf第2页

    试读已结束,剩余3页未读...

    9积分/C币 立即下载 >