论文研究-基于节点平均连接度的Ad Hoc网络分簇算法.pdf

所需积分/C币:9 2019-09-12 23:04:44 893KB .PDF
收藏 收藏
举报

Ad Hoc网络是一种多跳的自组织网络,网络是由移动的节点组成。Ad Hoc网络的许多应用都依赖层次结构的支持,簇结构是Ad Hoc网络中应用最为广泛的层次结构,而这种层次结构的形成和维护依赖于某种分簇算法。提出了移动节点的平均连接度计算方法,并在此基础上提出了一种新的分簇算法(MCDA),通过对算法进行分析和仿真测试,证明了该算法的有效性。
杨卫东:基于节点平均连接度的 ad hoc网络分簇算法 2009,45(25)113 能太少,应以满足系统要求和减少控制开销为准则。 (2)单位时间内节点重新加入簇的次数K,即节点在簇间 10 转移的次数。该指标用于说明在重新计算统治集的时间间隔内 的簇维护开销。为了减少开销,希望该指标越小越好。 (3)节点充当簇头时间是指各移动节点充当簇头的累计时 间。由于在 ad hoc网络中,节点是靠电池供电,若是某个节点 充当时间过长,就会过早耗尽其电池能量而成为网络通信的瓶 图5簇结构(最小ID) 颈。为此需要在节点间实施负载平衡,使所有的节点都可以比 较公平地充当簇头,也就是说尽可能将能量消耗均匀地分配到 各个节点上,以延长网络的寿命。该指标分布越均匀,说明网络 的负载平衡就越好,各节点充当簇头的公平性就越强。 6 下面借助模拟仿真的方法对最小I分簇算法、最高节点 11○ 12 度分簇算法和平均连接度分簇算法进行仿真,比较这三种算法 的性能指标 图6簇结构(最大连接度) 23.2仿真结果 在仿真测试中,节点数N=32,节点最大的移动速度为 V灬=5m/s,节点的传输范围r在5m-60m之间变化(在图8 中,节点的传输范围为25m),图中 LOWID表示最小I算法 HCDA表示最高节点度算法,MCDA表示节点平均连接度算法。 从图8中可以看出 LOWID算法中各节点充当簇头的时间 差异很大,ID号小的节点充当簇头的时间非常多(如节点1,基 9 本上是从头到尾都在充当簇头),ID号大的节点充当簇头的时 图7簇结构(MCDA) 间则非常少,因为这种算法本身就是侧重于选择I较小的节 点充当簇头,这会使得ID号小的节点负担较重,易过早地耗尽 表1系统拓扑结构的状态参数 其电池能量而使它成为网络通信的瓶颈。HCDA则倾向于选择 Wn Lowest-ID Highest-connectivity MCDA 具有最大连接度的节点作为簇头,虽有所改善,但改善不多。 MCDA算法则改善较大,因为该算法是通过计算节点的平均连 3/2 1/2 接度获得各自的权值,并以此为基础来对移动节点进行分簇 27/31/3 的,它对选择充当簇头的节点没有任何倾向性,使所有的节点 都有机会充当簇头,充分地体现了它的公平性,并起到了负载 678 421 平衡的作用。这也是提出这种分簇算法的意义所在。 8/3 2/3 从图9中可以看岀,簇头数随节点传输范围的增加而减 5/2 3/2 少,当传输范围大于30时,簇头数减少的速度逐渐变慢,但最 2232 7/3 1/3 ④④⑤⑥③②③⑦ ①①②①③①②① 终都收敛到1。图中可以看出HCDA得到的平均簇头数最少, 因为这种算法侧重于选择节点度较高的节点成为簇头,这样每 8/3 2/3 个簇内所包含的节点数就较多,可以产生较少的簇,从而降低 注:表中①⑦分别表示簇的序号,相同的数字表示这些节点分组投递的延迟,但该算法对簇内节点数没有限制,因而无法 分在相同的簇。黑体字表示该簇的簇头。 适应于某些对节点能力有限制的网终(如蓝牙协议,其主从结 构限制了每个主节点最多只能同时服务7个成员节点);另外 23算法的性能仿真及其结果分析 簇中的资源通常由簇内节点按照轮询的方式共享,所以当簇内 2.3.1模拟环境和性能指标 节点过多时,每个节点的平均吞吐量会急剧下降,且簇头的 模拟环境如下:仿真软件为 OPNET105;节点的移动模型数目减少了也意味着减少了信道的空间重用率。LOWD与 采用的是自组网经常使用的移动模型— Random Waypoint模MCDA的曲线走向比较接近,只是MCDA在传输范围25~45 型,在这种模式中,节点朝一个任意目的地运动,并带有周期间略低于 LOWID,在45以后略高于 LOWID。这主要是因为 性的停顿行为,节点的移动速度可以在(0,V灬)之间随机选择, LOWID是以选取最小的ID作为选择簇头的标准,而MCDA是 其中V表示节点移动的最大速度,单位是ms;节点的移动区以平均节点连接度作为选择标准,不是以提高网络的控制能力 域为一个100m×100m的区域;模拟时间为1000时间单位。和减少簇的数目为目的,所以它们的簇头数目比HCDA略高。 分簇算法的性能优劣与多个性能指标有关。在性能仿真过从图中可以看出传输范围为40时,HCDA的节点平均连接度 程中选取了3个主要指标:簇头数C、单位时间内节点重新加约为8,其他两种约为6,50时,HCDA约为12,其他两种约为 入簇的次数K和节点充当簇头时间。下面对这3个性能指标6.4,60时,HCDA约为14,其他两种约为8。 进行简要说明。 单位时间内节点重入簇的次数K(即节点在簇间转移的次 (1)网络中的簇头数目C(或簇的数目):该指标直接反映数)用于说明在重新计算统治集的时间间隔内的簇维护开销, 了分簇网络的结构和特性,分簇网络的簇头数不应过多,也不该指标越小越好。从图10可以看出:K随着节点传输范围的增 1142009,45(25) Computer Engineering and Applications计算机工程与应用 10000 : LOWID k LOWID LOWID 9000 家0.45 O MCDA HCDA HCDA 8000 怒0.40 ·HCDA 7000 O MCDA O MCDA 0.35 20 水6000 0.30 5000 水15 0.25 4000--2 区0.20 13000 2000 1000 0.05 0 5101520253035 102030405060 10203040 节点ID 传输距离 传输距离 图8节点充当簇头的时间 图9簇头数与传输距离的关系图10单位时间内节点重入簇次数与传输距离的关系 大先变大再变小,这主要是因为当节点的传输范围较小时,簇的 clustering in wireless networks[J].Telecommunication System, 2003 数目较多,簇内的节点数较少,甚至只有一个簇头,这时节点离 22(1-4):205-220 开原簇的概率较小。当节点的传输范围增大为30左右时k值达[2杨卫东,周杰英,张光昭 Ad hoc网络中一种基于权值的分簇算法J 到最大值,随后k值开始下降,这是因为尽管节点仍然保持移动 中山大学学报:自然科学版,2007,46(5):5- 状态,但出于簇头的传输范围较大,节点移出原簇的概率减小所3] YANG Wei-dong, ZHANG Guang-zhao. A weight- based clustering 致。同时也可以看到,对于指标K,各算法的性能差别较小,说明 algorithm for mobile Ad Hoc network( C/ /Proceedings of the 3nd MCDA算法与其他两种算法k值近似,即在该指标上性能相近 International Conference on Wireless and Mobile communications ICWMC'07,2007 3结论 [4] Gerla M, Tsai J T C Multicluster, mobile, multimedia radio network[JI 在分析现有分簇算法的基础上,提出了基于节点平均连接 ACM/Baltzer Journal of Wireless Networks, 1995. 1(3): 255-265 度的成簇策略,并据此提出了基于节点平均连接度的分簇算 [5] Lin C R, Gerla MAdaptive clustering for mobile wireless networks[J IEEE Journal on Selected Areas in Communications, 1997, 15(7) 法-MCDA。MCDA算法与 LOWID算法和HCDA算法一样具有 1265-1275 算法计算简单、实现方便和算法收敛快的特点;与 LOWID算法 和HCDA算法相比,在其他性能指标不改变的情况下,起到负61 Parekh a Kselecting routers in Ad- Hoc wireless networks]/pro- ngs of the SBT/IEEE International Telecommunications Sym 载平衡的作用。与 LOWID相比,它克服 LOWID算法倾向于选 posium, 1994 择I较小的节点作为簇头的缺点,它对选择充当簇头的节点 [7 Navidi W, Camp TStationary distributions for the random waypoint 没有任何倾向性,使所有的节点都有机会充当簇头,充分地体 mobility model[J]. IEEE Transactions on Mobile Computing, 2004 现了它的公平性;与HCDA相比,它克服了HCDA算法追求少 3(1). 簇头数目的缺点,改变了HCDA算法对簇内节点数没有限制 [8 Lin G, Noubir G, Rajaraman R Mobility model for Ad Hoc network 的缺陷,使它的适用性更强。通过对MCDA算法的分析和仿真 simulation[ C/proc of IEEE Infocom, 2004 测试,证明了这种算法的有效性。 9 Frodigh M, Johansson P Wireless Ad Hoc networkingThe art of networking without a network[J].Ericsson Review, 2000(4): 248-262 参考文献: [10] Cupta P, Kumar P. The capacity of wireless networks [J]IEEE [1] Nocetti F G, Gonzalez J S, Stojmenovic I Connectivity based K-hop Transaction on Information Theory, 2000, 46(2): 388-404 (上接107页) 攻击、篡改攻击的缺点,还保证了会议发起者V的前向安全 人的协议和该文的协议的通信量。 性。与文中提到的其他三个同类协议相比,该协议安全性最高, 表1通信量比较 通信量居中,由于在会议密钥建立协议中,安全性是最重要的 协议T2 X Yang等人 该文的协议 属性,因此,综合来看,该文协议的实用性最强。 通信量2m(m+3)m(m+6)m(3t+1)+4nmt2+2mt+2m+4n+m-t+1 在下面的分析中,TC表示2m(m+3),XC表示m(m+6),参考文献: [1] Tzeng W GA secure fault-tolerant conference key agreement pro- YC表示m(31+1)+4n,CC表示该文协议的通信量。因为m>n tocol[J].IEEE Transactions on Computers, 2002, 51(4): 373-379 (在实际实现中,服务器的数量应少于参与者的数量),因此有:121xuY. dentity- based fault- tolerant conference key agreement[ CC=mt2+2mt+2m+4n+mn-t+1<mt2+2mt+6m+mn-t+1s IEEE Transactions on Dependable and Secure Computing, 2004, 1 mt2+2mt+6m+mn<mt+2mt+6m+m2=m(m+6+t2+2t) (3):170-177 当t2+21<m+3时,就有YC<XC<CC<TC。也就是说,协议在3] Tseng Y M. An improved conference- key agreement protocol with 通信量上优于 Tzeng的协议但是次于Xun的协议和Yang等人 forward secrecy[J]. International Journal of Informatica, 2005, 16(2): 的协议。 [4 Yang Z K, Xie H T, Chen W Q, et al. An identity-based fault-to- lerant conference key distribution scheme[C /Parallel and Dis 6结论 tributed Computing: Applications and Technologies, 2006: 389-392 提出了一个改进的基于身份并且错误容忍的会议密钥分51 Shamir a. How to share a secret[J]. Communications of the ACMS.1. 配协议,改进的协议不但克服了原协议中存在的不能抵抗被动 ACM Press,1979,22(11)

...展开详情
试读 4P 论文研究-基于节点平均连接度的Ad Hoc网络分簇算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
    抢沙发
    一个资源只可评论一次,评论内容不能少于5个字
    weixin_38744435 欢迎大家使用并留下宝贵意见
    2019-09-12
    • 至尊王者

      成功上传501个资源即可获取
    关注 私信 TA的资源
    上传资源赚积分,得勋章
    最新推荐
    论文研究-基于节点平均连接度的Ad Hoc网络分簇算法.pdf 9积分/C币 立即下载
    1/4
    论文研究-基于节点平均连接度的Ad Hoc网络分簇算法.pdf第1页
    论文研究-基于节点平均连接度的Ad Hoc网络分簇算法.pdf第2页

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

    9积分/C币 立即下载 >