９２ 舰船电子对抗 第３Ｏ卷 主要评价参数：分簇数目就是簇首的数目，分簇 数目越多，所使用的信道数量就越大。当簇之间相 距两跳以上时，就可以使用同一信道，即空分复用， 这样可以有效利用为数不多的信道资源。 节点到节点的跳数对分组的传输时延有很大的 影响，采用最短路径算法，以增加网络的传输效率， 簇的大小（簇的规模）指簇内所含节点的数目，表示 使用同一信道的用户数目，簇的大小关系到每个节 点究竟有多少通信能力的问题。如果数目过大，在 每个节点业务量增大时，容易产生拥塞，而且每个节 点的碰撞概率也会大大增加，这必须通过簇首协调， 限制每个节点的增加。总之，簇的大小选择得越合 适，网络性能就越好。通常簇的大小可由功率控制 改变节点之间的通信链路状态来实现，簇的大小的 优化就是控制簇内节点数，以便每个节点乃至整个 网络达到最高的通信容量。 一个好的分簇算法应该使算法对节点的运动具 有一定的稳定性，即当只有一些节点发生移动或网 络结构发生较慢变化时，分簇结构不发生剧烈变化， 整个网络只是针对发生变化的部分进行分簇调整， 使脱网的节点在最短时间内就近加入簇，而其余部 分保持不变。簇首的频繁变动会导致簇首无法对其 簇进行有效控制，而失去对该区域的控制能力，同时 严重影响其它一些与之相关的协议性能的好坏，增 加用于重新控制的开销，并降低信道的利用率。下 面将介绍一种基于权值的Ａｄ ＨＯＣ网络分簇算法。 ２ 基于权值的Ａｄ ＨＯＣ网络分簇 算法 ２．１ 算法思想 本算法是一种基于权值的分簇算法，每个节点 被赋予１个权值ｗ（ ）．通过权值的比较来选择 簇首，进而生成整个簇。在权值的计算中，将综合考 虑节点所处的网络环境和本身状态。一个节点是否 适合担任簇首主要受到２个因素的影响： （１）节点的网络环境。包括 与其邻居节点之 间的相对速度和它的度Ｄ（ ）。这个相对速度越 低，则节点之间的相对位置变化越小，生成的簇结构 越稳定 临近节点的个数越多，则网络的统治集越 小，信息传输的路径越短。并且如果其与临近节点 的距离之和越小，临近节点收到的信号衰减也就相 应越少。所以选节点密集处的某适合节点为簇头， 一方面可以保证各节点收到正确的信号；另一方面 各节点依据距离调整自己的放射功率来保证与簇头 通信，能达到节能的目的。 （２）节点本身状态。包括节点的发射功率和节 点的剩余电池能量。簇首节点除了要完成本身的通 讯任务外，还要维护簇的结构、回应其成员节点的通 讯请求、簇间寻路等，因此应尽量选取功率大、电池 能量高的节点作簇头，因为功率大的节点作簇头，辐 射范围大，包含节点多，可以减少簇头的总个数，提 高网络的吞吐率。而电池能量大的节点作簇头，可 以保证节点扮演簇头的时间长，减少簇的重构，增加 簇的稳定性。因此簇首节点的选取应该满足一定的 处理能力和能量状态要求，才不至于成为通讯瓶颈。 节点 的权重计算公式为： Ｗ（ ）一Ｗ Ｓ ＋Ｗ Ｓｌ。 （１） 式中：Ｗ（ ），Ｗ Ｗｌ。 ，Ｓ Ｓｌ（１ｃ分别为节点 的 权值，网络状态权重，本机状态权重，网络状态值和 本机状态值，且有ｗ ＋Ｗ－。。一１。 调整ｗ 和ｗ。。 可以适应多种网络环境。例如 当网络拓扑变化较大，节点相对移动较怏，而各个节 点的处理性能基本相当时，就可以把ｗ 和ｗ 设 置大一点以保证簇结构的稳定性。如果情况相反， 则可以调整ｗ 。 和ｗ。。 的值以便选择处理性能更强 的节点担任簇首，避免传输瓶颈的产生。 ｓ 用来描述当前的网络状态。它本身也是一 个加权和。它包括节点与邻居节点的相对移动速度 Ｖ Ｉ（ ｒ（ ））和节点 的度Ｄ（ ）。这里相对速 度是以连续２个报文的接收功率Ｐ的比值作为节 点相对移动性测量的依据，称之为节点 对应邻居 节点 ，的相对移动量。其计算公式如下： ｐ ｒｅ】（ｉ，Ｊ）一１０ｌｇ （２） 』ｉ一・ｉ 所以网络状态值Ｓ ，的计算方法如下： Ｓ 。 一Ｗ１×Ｖ ｒｅ１（ 。ｒ（Ｖ ））＋Ｗ２×Ｄ（Ｖ ）（３） 式中：ｗ ＋Ｗ 一１。调整ｗ 和ｗ 可以使网络参 数Ｓ 适应于多种网络环境。 Ｓ。。 用来描述节点本身的状态。它包括节点的 计算速度、存储器大小和电池剩余量。这些内容反 映了节点对数据包的处理能力和自身的能量状态。 它是衡量一个节点是否适于担任簇首的另一个重要 因素。其计算方法如下： Ｓｌ。 ＝Ｗ ×Ｃ（Ｖ．）＋Ｗ２×ＰＷ（Ｖ ） （４） 式中：Ｃ（Ｖ ）为本机性能量化值，它主要以计算速 度、存储器大小为基础；Ｐｗ（Ｖ 为剩余能量的量化 维普资讯 http://www.cqvip.com
第６期 刘长利等：一种用于Ａｄ Ｈｏｃ网络的分簇算法 ９３ 值，它以电池剩余能量为基础。 ２．２ 算法描述 本算法是一个动态、分布执行的算法。每个节 点被赋予１个全局唯一的ＩＤ号。算法用ＨＥＬＬ（） 消息建立和维持与相邻节点的链路。节点 用 ＣＨ（Ｖ ）消息宣布自己为簇首节点。用ＪＩＯＮ（Ｖ，， Ｖ ）消息请求加入以Ｖ，为簇首的簇，成为其成员节 点。若Ｖ，为簇首节点，则用Ｒ（Ｖ ，Ｖ，）消息拒绝节 点Ｖ 加入请求，或者用Ａ（Ｖ ，Ｖ，）消息接受节点 的加入请求。 ２．２．１簇的构建 在网络初始建簇或有新节点Ｖ加入时，都将通 过初始化过程来构建簇，决定节点在网络中应该担 当的角色。各个节点通过ＨＥＬＬＯ消息建立邻接链 路，计算出初始权值，并通过ＨＥＬＩ Ｏ消息来传输自 己的权值和可用度。各个节点通过比较邻居节点的 权值来选择执行相应的子过程。若节点Ｖ 判断自 己为相邻节点中权值最大的节点，则向所有邻居节 点发送ＣＨ（Ｖ ）消息，宣布自己成为簇首节点。开 始接受邻居节点的加入请求，同时在ＨＥＬＬＯ消息 中设置表明自己为簇首的标志位和所有已经接受的 成员节点的ＩＤ号。若节点Ｖ 判断自己邻接节点中 Ｖ，的权值大于自己，同时Ｖ 发出了ＣＨ（Ｖ，）消息， 那么节点 发出ＪＩＯＮ（Ｖ ，Ｖ ）消息，请求加入。 若节点Ｖ 收到了簇首Ｖ，发出的Ａ（Ｖ ，Ｖ ）消息或者 在Ｖ，的ＨＥＩ ＬＯ消息中设置表明自己成为成员节 点的标志位和簇首的ＩＤ号，则Ⅵ判断自己的请求 被拒绝。若节点Ｖ 收到Ｖ，的Ｒ（Ｖ ，Ｖ，）消息或者在 ２个连续Ｖ，的ＨＥＩ ＬＯ消息中找不到自己的ＩＤ号， 则Ｖ 判断自己的请求被拒绝。若节点 发现所有 权值大于自己的邻居节点，是簇首节点但可用度为 零，或者作为成员节点加入其它簇，那么节点Ｖ 将 发出ＣＨ（Ｖ ），宣布自己成为簇首。 ２．２．２簇的合并 如果一个临时簇头ＣＨ（Ｖ ）被包含在另一个簇 头ＣＨ（Ｖ，）里面，则子簇头ＣＨ（Ｖ ）连同它的成员 一同加入到父簇头中，对于合并有一定的上限规则， 例如跳数和节点数等。在合并之后，这一高级的簇 头被作为新选簇的簇头。 ２．２．３簇的更新和维护 在簇的初始化完成以后，随着节点的移动，能量 下降以及障碍物等因素的影响，网络的拓扑结构会 发生变化，网络链路会发生新建和失效。当发生下 列情况时都有可能使簇内成员组成发生变化：（１）１ 个新节点进入网络；（２）１个已存在的节点离开网 络；（３）１个节点进入新的簇头覆盖区；（４）１个节 点离开现在的簇头覆盖区。 因为簇头与每个节点之间定期进行通信，当簇 头确认１个节点离开该簇时，则将该节点从簇内成 员删除：当收到新的节点信息且满足所需的条件（如 跳数、节点数）时，则加入该节点为簇成员，若不满足 条件，通知该节点。该节点则需在运动中继续寻找 新的簇头，若找不到，宣称自己为新的簇头，引发簇 的重构。当移动的两簇头之间的距离小于等于某一 规定要求时，也要引发重构。 ３ 结束语 本文提出的算法综合考虑了Ａｄ Ｈｏｃ网络节点 本身状态和网络环境对网络分簇的影响，以权值作 为选举簇首的关键因素，从而使该算法更适合于多 种网络环境下的大规模Ａｄ Ｈｏｃ无线网络管理，更 有利于在此基础上进行的路由协议、调度算法等的 设计。然而簇的大小究竟多少才能更好地保证整个 网络的负载平衡，提高网络吞吐率，更好地进行簇的 维护等，这些都是算法需要改进的地方。此外如何 在基于簇的管理基础上设计具有节能策略、安全保 障、组播功能和ＱｏＳ支持等扩展特性的路由协议等 都需要进一步深入研究。 参考文献 ［１］ Ａｌｗａｎ Ａ，Ｂａｇｒｏｄｉａ Ｒ，Ｂａｍｂｏｓ Ｎ，ｅｔ ａ１．Ａｄａｐｔｉｖｅ ｍｏ— ｂｉｌｅ ｍｕｌｔｉｍｅｄｉａ ｎｅｔｗｏｒｋｓ［Ｊ］．ＩＥＥＥ Ｐｅｒｓｏｎｎａｌ Ｃｏｒｎ— ｍｕｎ，１９９６，３（２）：３４—５１． ［２］ Ｍａｉｎａｋ Ｃｈａｔｔｅｒｊｅｅ，Ｓａｊａｌ Ｋ Ｄａｓ，Ｄａｍｌａ Ｔｕｒｇｕｔ ＷＣＡ． Ａ ｗｅｉｇｈｔｅｄ ｃｌｕｓｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｍｏｂｉｌｅ ａｄ ｈｏｃ ｎｅｔ— ｗｏｒｋｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｃｌｕｓｔｅｒ Ｃｏｍｐｕｔｉｎｇ，Ｓｐｅｃｉａｌ ｉｓｓｕｅ ｏｎ Ｍｏｂｉｌｅ Ａｄ ｈｏｃ Ｎｅｔｗｏｒｋｉｎｇ，２００２（５）：１９３—２０４． Ｅ３］ Ｗａｎｇ Ｈａｉ－ｔａｏ，Ｔｉａｎ Ｃｈａｎｇ，Ｚｈｅｎｇ Ｓｈａｏ—ｒｅｎ．Ａ ｎｏｖｅｌ ｃｌｕｔｅｒｉｎｇ ａｌｇｏｒｉｔｈｍ ｉｎ ａｄ ｈｏｃ ｎｅｔｗｏｒｋ ａｎｄ ｉｔｓ ｐｅｒｆｏｒｍ— ａｎｅｅ ｓｉｍｕｌａｔｉｏｎｓ［Ｊ］．Ｊｏｕｒｎａｌ ｏｆ Ｓｙｓｔｅｍ Ｓｉｍｕｌａｔｉｏｎ， ２００３，１５（２）：１９３—１９７． ［４］Ｇｅｒｌａ Ｍ，ｓａｉ Ｊ Ｔ Ｃ．Ｍｕｌｔｉｃｌｕｓｔｅｒ ｍｏｂｉｌｅ，ｍｕｈｉｍｅｄｉａ ｒａ— ｄｉｏ ｎｅｔｗｏｒｋ［Ｊ］．Ｗｉｒｅｌｅｓｓ Ｎｅｔｗｏｒｋｓ，１９９５，１（３）：２５５ —２６５． ［５］Ｋａｉｘｉｎ Ｘｕ，Ｘｉａｏｙａｎ Ｈｏｎｇ，Ｇｅｒａｌ Ｍ．Ａｎ ａｄ ｈｏｃ ｎｅｔｗｏｒｋ ｗｉｔｈ ｍｏｂｉｌｅ ｂａｃｋｂｏｎｅｓ［Ｊ］．ＩＥＥＥ．ＩＣＣ，２００２（５）：３１３８ —３】４３．
因篇幅问题不能全部显示，请点此查看更多更全内容