一种社会化间断连接网络动态地址分配及网络性能优化方法

摘要

本发明请求保护一种社区化间断连接网络动态地址分配方法及网络优化方法，涉及无线网络技术领域。本发明针对现有间断连接网络中节点地址固定不变，不适应社会化间断连接网络的动态特性，本发明结合社会化间断连接网络的特性，提出一种反映节点相对地理位置的编址方法，进而设计了适用于社会化间断连接网络动态地址分配机制，能够有效地解决了间断连接网络动态变化时节点地址分配问题，并有利于设计路由协议为数据传输选择合理的下一跳中继节点。

说明书

技术领域

本发明涉及无线网络领域，尤其涉及社会化间断连接网络的动态地址分配及 网络性能优化。

背景技术

随着大量低成本，具备短距离通信能力的智能设备(如手机、PDA、传感器 等)大量普及，使移动自组网(Mobile Ad Hoc Network，MANET)应用得到了快 速发展。传统的MANET路由协议要求源节点和目标节点之间至少存在一条完整的 路径，但在许多实际环境中，由于节点移动、网络稀疏等原因，导致节点之间无 法实现有效通信。间断连接网络利用节点移动形成的相遇机会，以“存储—携带 —转发”的路由模式逐跳实现节点间通信。虽然，此种类型网络中，数据传输过 程需要多个中继节点辅助，传输延迟较大，但传输成本低，特别适用于不易架设 网络基础设施的环境。因此，受到了国内外研究人员的广泛关注。

根据社会网络理论，不同的个体在社会中所表现的重要程度并不相同，因此， 相应终端所组成的网络也呈现“小世界”现象，即依托各种移动终端所组成的间 断连接网络具有较强的社会性。

社会化间断连接网络是指具有短距离无线通信接口的个人移动终端组成的 具有社会性质的网络。除了具备间断连接网络中的节点移动迅速、网络拓扑时变 等特点外，社会化间断连接网络中，节点之间的关系相对稳定且存在一定的依赖 性，存在节点聚集现象，从而形成不同的社区。按照节点当前所处社区情况，可 将其划分为两种状态，分别为本地状态和漫游状态。本地状态下，节点以较小的 概率离开社区，而处于漫游状态的节点则以较大的概率返回归属社区。此外，社 区内各个节点的重要程度以及活跃程度并不相同，某些节点在社区内部相对活 跃，经常往返于不同的社区之间，增加了社区间的联系，即中心节点。在社会化 间断连接网络中，节点存在以下特点：1)节点之间聚集形成社区；2)社区内， 节点与其邻居节点相遇频繁，通信机会较多；3)网络动态性较强，允许节点自 由的加入和离开。显然，数据传输过程的实现以节点按照一定的规则进行编址为 前提条件，合理有效的地址分配方法将能够有效地降低网络地址资源消耗情况， 同时，节点可以根据地址确定归属位置，从而更加合理地选择中继节点执行转发 任务，进而提升网络整体性能，因此，对此种网络的节点地址分配和网络性能优 化需要综合考虑上述各个方面的因素。

通常情况下，节点地址分配可分为静态地址分配和动态地址分配两类。静态 地址分配机制根据预先定义的网络寻址规划为节点分配地址，节点所获得的地址 需要以手动方式进行修改。此类地址分配方法简单、方便，但不适合动态性较强 的间断连接网络。与之相对，动态地址分配机制则是在节点加入到网络时，通过 某个与协议特定相关的过程来获得地址，节点在使用动态地址时，每次加入到网 络之后所获得的地址并不相同，对于地址资源有限的间断连接网络来说，此种方 式能够有效提高网络地址资源利用率。

现有的社会化间断连接网络路由协议均假定节点在进入网络之前已经成功 获取了网络地址，且该地址在节点运行过程中不会改变。然而这对于动态性较强 的社会化间断连接网络来说，当网络规模增大时，将严重的影响其性能。因此， 有效的动态地址分配方法能解决网络动态变化时节点地址分配问题，避免节点地 址冲突，确保全网络节点地址的唯一性，进而为中继节点选择提供充分的依据， 达到改善网络的性能的目的。

目前，国内外研究人员针对动态地址分配方法和基于节点行为的网络性能优 化方法进行了相关研究。杜治高，钱德沛，刘轶等在“面向分簇无线传感器网络 的两层动态地址分配协议”【高技术通讯，2011，21(3)：235-241】文章中提 出了一种两级动态地址分配(TTDA)协议，即基站为簇头分配地址，簇头为簇成员 分配地址。Doss R C，Chandra D，Pan L等在“Lease based addressing for  event-driven wireless sensor networks”【In：Proc.of the IEEE Symposium  on Computers and Communications，Sardinia.Italy，2006：251-256】文章 中采取集中分配方式，由基站统一为其他节点分配地址。Kim H，Kim S C，Yu Misun 等在“DAP：Dynamic Address Assignment Protocol in Mobile Ad-hoc  Networks”【In：Proc.of ISCE 2007.IEEE International Symposium on  Consumer Electronics，2007：1-6】文章中提出一种新的自助配置地址管理协 议，该协议利用分布式地址池给新加入的节点分配地址。Nesargi S，Prakash R 在“MANETconf：Configuration of Hosts in a Mobile Ad Hoc Network”【In： Proc.of IEEE INFOCOM’02，Newyork，USA，2002：1059-1068】文章中提出一 种分布式动态地址分配协议，节点地址从地址空间中随机选择，然后使用路由协 议的路由发现阶段的信息来检测重复地址。孙利民，熊永平，马建在“机会移动 传感器网络中的自适应数据收集机制”【通信学报，2008，29(11)：186-193】文 章中提出一种自适应的数据收集机制，该机制利用节点的剩余能量和相遇概率来 估计节点的转发概率，根据节点对数据分组的转发概率来执行转发操作。同时， 以节点转发概率计算得到的数据分组重要因子来进行缓存管理。LeBrun J，Chuah  C，Ghosal D等在“Knowledge-Based Opportunistic Forwarding in Vehicular  Wireless Ad hoc Networks”【in：Vehicular Technology Conf，2005，vol.4： 2289-2293】文章中提出一种机会转发策略，该策略节点采用当前位置和移动方 向对数据分组转发进行决策，当相遇节点与目的节点距离较近或者正向目的节点 移动时，数据分组的携带节点则将数据分组继续转发给该相遇节点。

社会化间断连接网络的拓扑结构具有较强的动态性，同时网络中节点之间存 在较强的依赖关系，因此，节点之间的相对位置信息与其社会关系直接相关。上 述文献中提出的动态地址分配及网络性能优化方法均没有考虑节点的归属位置， 同时，节点在数据转发时无法获取与其邻居节点的相对位置信息，难以合理地选 择中继节点，降低了网络性能，不适合在社会化间断连接网络中使用。为了有效 地提高网络的性能，本发明在社会化间断连接网络下引入反映节点归属位置的动 态地址编址方式，提出一种社会化间断连接网络动态地址分配及网络性能优化方 法。节点通过动态地址可以更加灵活地加入和离开网络，网络运行不受影响，同 时，所提出的方法为路由协议设计以及中继节点选择提供依据，能够有效提高数 据成功投递率，降低网络平均时延等。

发明内容

本发明所要解决的技术问题是：现有间断连接网络中节点地址的固定不变， 不适应社会化间断连接网络的动态特性，同时，节点在数据转发时无法获取与其 邻居节点的相对位置信息，难以合理地选择中继节点，针对此问题，本发明结合 社会化间断连接网络的特性，提出一种反映节点归属位置以及相对位置的编址方 法，进而设计适用于社会化间断连接网络动态地址分配及网络性能优化机制，能 够有效地解决间断连接网络动态变化时节点地址分配问题，并有利于设计路由协 议为数据传输选择合理的下一跳中继节点。

本发明解决其技术问题所采用的技术方案是：提出一种社会化间断连接网 络动态地址分配方法，在社会化间断连接网络中，根据节点之间的相遇频率和平 均相遇频率，将网络拓扑逻辑上划分成若干个社区。在各个社区内以分布式方式 选取中心节点；中心节点之间通过协商从地址树中获取地址子集，将节点地址表 示为由社区号和节点号组成的多级编址；利用地址空间映射，将节点的多维地址 空间映射为一维地址空间，并根据节点之间的相邻程度为其归属社区内节点分配 地址。

在上述基础上，本发明提出一种社会化间断连接网络优化方法，节点根据 与其相遇节点之间的逻辑距离完成数据转发判定以及相关操作。

在社会化间断连接网络中，节点之间的关系相对稳定且存在一定的依赖性， 存在节点聚集现象，从而形成不同的社区。节点以较大的概率在其归属社区内移 动，以较小的概率离开归属社区去往其他社区，归属社区不同的节点相遇概率较 小。综合考虑节点活跃度、节点内存容量、节点能量、节点出社区概率等因素， 在各个社区内以分布式方式选取中心节点，通过各个社区间的协商过程，每个中 心节点都从地址空间获得相应的连续地址子集。当社区较大时，可以增加中心节 点数目，以免由于中心节点过载导致某些节点无法得到地址或者更新不及时。节 点地址采用两级结构，由社区号和节点号组成。按照节点地址社区号，通过等分 法，将地址空间构造成一颗地址树，地址树上的每个非叶子结点(除根结点外) 都是一个等大小的连续地址子集。社区中心节点根据本社区的节点数，并与其他 节点进行协商，从中选取一个连续地址子集，进而，有效地避免网络中出现地址 冲突。

当新的节点加入社区时，中心节点根据节点之间的相邻程度为其分配地址， 同时，当有节点离开网络时，中心节点负责其地址回收，以有效地利用有限的地 址资源。

本发明中，节点之间的相邻程度采用预定时间内节点之间的相遇次数进行 描述，相遇次数较多的节点其相邻程度较高，其地址的逻辑距离较小。网络中的 各个中心节点保存本社区可分配的地址范围和地址表，其地址表记录了本社区中 节点的ID和地址。当有新的节点加入社区时，先向中心节点发送请求地址消息， 中心节点通过查找地址表获取新加入节点的邻居节点地址以及尚未被分配的地 址信息，并采用地址映射方法，即将节点的多维地址空间映射为一维地址空间， 按照节点地址的逻辑距离，从尚未被分配的地址中选取新节点的地址。当有社区 中的节点要离开网络时，该节点向中心节点发送离开报告消息，中心节点则根据 收到的消息查找地址表，并删除其记录。

本发明提出的动态地址分配方法充分考虑到社会化间断连接网络的拓扑动 态性，有效地解决了网络拓扑动态变化过程中地址分配问题，避免了整个网络范 围内的节点地址冲突。同时有利于节点根据数据目的地址合理地选择下一跳中继 节点。当源节点向目的节点发送数据时，若两者属于同一个社区，则数据就只在 归属社区内的节点间进行传播，不需要扩散到归属社区之外的其他社区。相反， 则源节点可以通过判定与其相遇节点的归属社区情况，寻找属于目标社区的节点 作为中继节点，以携带数据至目的社区，进而将数据转发至目的节点。通过合理 地选择中继节点，数据传输过程中的转发次数得到了有效控制，提高了网络性能。

附图说明

图1动态地址分配流程图。

图2动态地址结构和动态地址表。

图3地址树。

图4二进制五维地址空间中数据传输路径示例。

图5五维地址空间与一维地址空间的转换。

图6动态地址分配。

具体实施方式

在社会化间断连接网络中，人类个体之间的活跃度以及重要度之间存在较 强的差异；同时，具有某种相同属性的人群呈现出聚集特性，形成社区结构。显 然，人类所携带的终端也具有相应的属性。活跃度和重要度较高的节点以较大的 概率频繁地出现在各个社区之间，另外，大部分节点在社区内每个节点都有归属 位置，节点以较高的概率在社区内部活动，以较低的概率离开本地社区进入其他 社区。

根据社会化间断连接网络的特点，其模型属性可抽象为以下几个方面：

1)网络中每个节点属于且仅属于一个社区，即归属社区；2)在归属社区内， 节点选取一个固定的位置作为自己的归属地点；3)节点以一定的概率返回其归 属地点；4)社区内节点按照一定的概率离开其归属社区，进而漫游至其他社区； 5)离开归属社区的节点将在目标社区随机选取一个位置作为目的地；6)节点到 达目的地后将随机停留一段时间，然后选择下一个目的地继续移动。

如图1所示为本发明动态地址分配流程图。

在社会化间断连接网络中，每个节点都记录一定时间T内与其他节点的相 遇状态，并计算相遇频率EF和平均相遇频率(如节点N_a与节点N_b的相遇频 率为EF(N_a，N_b)；节点N_a与网络中其它所有节点的平均相遇频率为)； 进而，通过两个参数的数值比较将社会化间断连接网络划分为若干个社区；在每 个社区内选取一个中心节点，根据网络中的节点数计算地址长度，并构造地址树； 各个社区的中心节点之间进行协商，从地址树中获取连续的地址子集作为各自归 属社区的节点地址；中心节点接收网络中其它节点的消息，可根据消息类型进行 相关处理，若为非管理消息(管理消息包括地址请求消息和报告离开消息)，中 心节点存储或者转发该消息；若为地址请求消息，并请求该中心节点的归属社区， 中心节点查找地址表，依据社区内节点之间的相邻程度，进行地址空间映射，为 地址申请节点分配一个与其邻居节点相近的地址；若为离开消息，中心节点则查 找地址表，删除该节点的记录回收其地址。

利用社会化间断连接网络的基本特性，本发明结合集中式和分布式地址分 配方法的优点提出了一种社区化间断连接网络动态地址分配及网络优化方法。主 要包括社区划分、节点地址、节点距离计算、地址映射和地址分配。

为便于对本发明的理解，以下对具体实现方式进行具体描述。

一、社区划分

以节点之间的相遇频率和平均相遇频率对网络进行社区划分。

根据社会化间断连接网络的基本特性，社区内的节点相遇频率大，社区间 的节点相遇频率较小。因此可以将节点之间的相遇频率(Encounter Frequency， EF)和平均相遇频率作为划分社区的依据。在社会化间断连接网络中，每个节点 都记录一定时间T内与其他节点的相遇状态，并计算相遇频率EF和平均相遇频 率相关参数定义如下：

1)EF(N_a，N_b)：节点N_a与节点N_b的相遇频率，其值可由公式(1)得到

EF(N_a，N_b)＝n(N_a，N_b)/T           (1)

其中n(N_a，N_b)是节点N_a和节点N_b在时间T内的相遇次数，显然，EF(N_a，N_b)＝EF(N_b， N_a)。

2)节点N与网络其他节点相遇频率的平均值，即平均相遇频率， 其值可由公式(2)得到

$\overline{\mathrm{EF}\left(N\right)}=\frac{n_{\mathrm{total}}\left(N\right)}{T\times n_E}---\left(2\right)$

其中n_total(N)是节点N在T时间内与网络中其他所有节点相遇的总次数，n_E是节 点N在时间T内相遇的节点总数。

网络中的节点都记录与其他节点在一段时间T内的相遇状态。通过计算可 以得到上述两个参数：当节点N_a和节点N_b同时满足式(3)中的两个条件：

$\left(\begin{array}{c}\mathrm{EF}(N_a,N_b)>\overline{\mathrm{EF}\left(N_a\right)}\\ \mathrm{EF}(N_b,N_a)>\overline{\mathrm{EF}\left(N_b\right)}\end{array}\right)---\left(3\right)$

则节点N_a和节点N_b属于同一个社区。通过此种方式，将网络中的节点划分成若 干社区。

二、节点地址表示

将节点地址表示为由社区号和节点号组成的多级编址。

网络中节点N可以表示为：N(x₁x₂…x_i…x_d)，其中(x₁x₂…x_i…x_d)为节点N 的地址，x_i∈{0，1，...，M-1}，1≤i≤d，d为节点地址维数，M表示进制 (可以为任意进制，如二进制、八进制、十六进制等)。采用上述方法，节点N 的第i维地址值可表示为D_i(N)。若节点N₁和节点N₂除了第i维地址值不同， 其它维的地址值都相同，即D_i(N₁)≠D_i(N₂)且D_j(N₁)≠D_j(N₂)，1≤j≤d， j≠i，那么它们互称为第i维相邻节点；在d维M进制地址空间中，节点的 邻居总数为(M-1)×d。进而，若互为相邻的节点N_a和节点N_b满足D_i(N_b)＝[D_i(N_a)+1]％M，则称它们为一步相邻节点。

根据社区化间断连接网络的社区性，本发明中节点地址采用多级编址方式， 其结构如图2(a)所示。地址由社区号和节点号组成，社区号表示节点所在的社 区编号，它的长度随网络中社区数而定，如果社区数越多，那么所占用的地址空 间越大。编址方法可采用任何进制的地址，但为了简明扼要，下文均以二进制的 五维地址来举例说明。假设网络被划分为4个社区，只需采用地址的前两位定义 社区号即可。节点号具体指示网络中的节点，它的长度与社区内的节点数有关。 节点号有效地保障了节点地址在社区内唯一，而社区号保障了该社区号码无冲 突。通过所述地址编码方式，可获得如图2所示的两级地址树。在地址树中， Level_1中的结点是由社区号唯一确定的地址子集，其中的叶子结点(即Level_2 中的结点)为实际的节点地址。

三、节点间的逻辑距离

根据节点的地址确定节点之间的逻辑距离，节点计算相应的逻辑距离以对 数据携带节点N_c和相遇节点N_e之间数据的转发操作进行决策：若相遇节点N_e与 目的节点N_d的地址距离小于数据携带节点N_c与目的节点N_d的地址距离，则进行 数据转发。否则，节点不对该数据转发，以降低网络资源开销。

对于网络中任意两个节点N_a和N_b，可根据它们的地址来确定它们之间的逻 辑距离，即物理位置的相近程度，记为L_Logic(N_a→N_b)，其数值的计算方式可根据 海明距离来确定。将节点N_a和N_b的各维对应地址值进行比较，其地址值不同的 维数称为两节点之间的海明距离，记为：|N_a→N_b|。对于节点N_a和N_b，令Δ_ab(k)节 点N_a和N_b第k地址是否相等，若相等，Δ_ab(k)＝0，否则Δ_ab(k)＝1，即

${\Delta }_{\mathrm{ab}}\left(k\right)=\left(\begin{array}{cc}0,& D_k\left(N_a\right)=D_k\left(N_b\right)\\ 1,& D_k\left(N_a\right)\ne D_k\left(N_b\right)\end{array}\right)---\left(4\right)$

则节点N_a和N_b之间的海明距离可以表示为：

$|N_a\to N_b|=\underset{k=1}{\overset{n}{\Sigma }}{\Delta }_{\mathrm{ab}}\left(k\right)---\left(5\right)$

显然，|N_a→N_b|＝|N_b→N_a|，且|N_a→N_b|≤d，其中d为地址空间的维数；当 |N_a→N_b|＝0时，则表示节点N_a和N_b的地址完全相同。

对于采用“存储-携带-转发”方式传输数据的社会化间断连接网络来说， 节点间的地址可以直观地反映其相邻程度，进而，可根据节点的逻辑距离对数据 携带节点N_c和相遇节点N_e之间数据的转发操作进行决策：

|N_e→N_d|＜|N_c→N_d|         (6)

若相遇节点N_e与目的节点N_d的地址距离小于数据携带节点N_c与目的节点N_d的地址距离，则进行数据转发。否则，不转发。根据公式(6)可以为数据传输 选择合理的下一跳中继节点，达到优化网络性能的目的。

四、地址空间映射

将节点的多维地址空间映射为一维地址空间，将多维地址空间进行M等份 d次递归划分，形成一维地址空间。其中d为多维地址空间的维数，M为进制， 如二进制，则M＝2；八进制，则M＝8等等。

在数据传输过程中，从源节点到目的节点存在多条路径，且各个路径的传 输性能并不相同。而间断连接网络路由协议通过控制数据分组的转发跳数，以较 短路径来降低网络开销。同样地，在基于社区的间断连接网络中，利用节点的社 会性，携带分组的节点尽可能地为数据分组选择与目的节点同属于一个社区的节 点作为该数据分组的中继节点，一方面以提高分组携带节点与目的节点的相遇可 能性来达到成功传递数据，另一方面以减少数据分组转发跳数来降低网络开销， 从而提升网络性能。如图4所示，地址的前两位表示社区号，后三位表示节点号， 当源节点N_s向目的节点N_d发送数据时，路径N_s→N_a→N_d比路径N_s→N_b→N_f→N_d要 优。此问题在任意d维地址空间中普遍存在，且随着维数的逐渐增加，问题越突 出。如果d＝1，那么N_s→N_d为最优路径。因此将多维地址空间映射到一维地址空 间有利于节点为数据传输选择合理的下一跳中继节点，同时也有利于地址分配过 程中进行合理的地址选择。地址空间映射方法描述如下：

在实际网络中，节点地址空间可根据网络的规模确定。假设采用上述实例 中的二进制五维地址，即M＝2，d＝5，则其空间大小(即地址数)N_address＝M^d＝32。 先构造一个对应的一维线性空间，大小也为32。首先将该地址空间分成M等份， 对每一子等份再划分成M等份，依此类推，直到d次递归划分。如图5所示， 通过上述方式，总共进行5次递归2等分的划分，最后可以形成32等份的一维 地址空间。

节点N(x₁x₂…x_d)从三维空间映射到一维空间的规则如下：首先从整个线 性地址空间的M个大等份中找到第x₁等份，然后从第x₁等份的M个子等份中找 到第x₂个子等份；依次类推，最后在从这第x_d-1个子等份中找第x_d等分，这样就 找到了节点N在一维线性地址空间中的位置。例如，节点N₁(00001)、N₂(00101)、 N₃(01100)、N₄(01111)、N₅(10100)，按照上述的规则，可以找到它们在一维线性 地址空间中的对应位置，如图5所示。

通过这种方法，可以将任意一个多维空间映射为一维空间，从而使地址分配 时地址选择更加直观、方便和合理，同时也有利于数据携带节点为数据传输选择 合理的下一跳中继节点。

五、动态地址分配方法

根据社会化间断连接网络的社区性，本发明采用分布式和集中式动态地址分 配相结合的地址方法。在网络中的各个社区以分布式的方式选取中心节点，该节 点负责其归属社区内的动态地址分配。从每个社区的角度来看，动态地址分配是 采用集中式的地址分配方式，但从整个网络的角度来看，动态地址分配为分布式 过程。

根据网络中的节点数，选择合适的地址长度构造一颗地址树，中心节点之间 通过协商从地址树中选取地址子集，以确保每个社区的地址子集不同。中心节点 根据节点之间的相邻程度为其归属社区内的节点分配地址。

在社会化间断连接网络中，每个社区选择一个中心节点，中心节点的选取应 综合考虑以下因数：1)节点活跃度A；2)节点缓存容量B；3)节点能量E；4) 节点出社区概率P。其中缓存容量、能量和出社区的概率是节点的固有属性，可 以由节点存储的本地信息得到，而节点的活跃度则需利用节点之间的相遇状态来 获得。节点活跃度定义如下：

令在时间T内节点N相遇节点集合为Ω，节点N与集合Ω中的任一节点X的 相遇次数为X∈Ω，节点N与社区内其他节点的平均相遇次数为节 点X对节点N的依附性为Γ_X(N)，若

${\Gamma }_X\left(N\right)=\left(\begin{array}{cc}1,& n_{X\leftrightarrow N}\ge \overline{n\left(N\right)}\\ 0,& n_{X\leftrightarrow N}<\overline{n\left(N\right)}\end{array}\right)---\left(7\right)$

则节点N的活跃度如公式(8)所示：

$A_N=\underset{X\in \Omega }{\Sigma }{\Gamma }_X\left(N\right)---\left(8\right)$

中心节点的综合能力C应满足：

C_max＝αA/A_max+βB/B_max+γE/E_max+λP；α+β+γ+λ＝1

                                                  (9)

其中α、β、γ、λ分别表示节点活跃度A、节点缓存容量B、节点能量E、节 点出社区的概率的权重P，A_max、B_max、E_max分别表示社区内节点的最大活跃度、最 大缓存容量、最大能量。在社区内，综合能力满足上述条件的节点作为中心节点， 即选择综合能力最大的节点作为其中心节点。当社区区域增大时，可以适当的增 加中心节点。

节点地址长度(即地址维数d)与网络的大小(即网络中的节点数n)以及 节点地址进制M存在如下对数关系：

d＝log_Mn        (10)

选择初始的地址长度，构造一颗地址树。中心节点之间通过协商从地址树中 选取地址子集，以确保每个社区的地址子集不同，同时也能确保全网中每个节点 地址的唯一性，进而，在社区内进行地址分配。当网络增大时，节点地址将出现 紧缺。这时，可在节点地址的社区号和节点号之间补0以扩充节点地址长度。但 是计算节点之间的海明距离时，如果两节点的地址长度不等时，需要以同样的方 式补0更新后，再进行计算。这样，既不会影响节点之间的海明距离，同时又可 以增加地址数，解决地址紧张的问题。

在社区内，中心节点建立一个如图2(b)所示的地址表，它记录社区中节点 的ID和地址，中心节点周期性采集节点之间的相遇次数。中心节点根据社区内 节点之间的相邻程度，给相邻的节点分配相邻地址，以此来反映节点之间的相遇 可能性。其中节点之间的相邻程度是由一段时间内节点之间的相遇次数决定的， 在相同的时间内，节点之间的相遇次数越多，它们之间的相遇可能性就越大，因 此它们之间的相邻度越大。

为了适应间断连接网络的动态特性，需要考虑随时有新的节点加入和离开 网络，因此，如何为这些新加入的节点分配地址是一个关键问题。为了确保节点 地址在网络中的唯一性，中心节点在为新加入社区的节点分配地址之前，应知道 其归属社区地址子集中尚未被分配的地址以及其邻居节点的地址。当有新的节点 加入社区时，先向中心节点发送地址请求消息，中心节点收到地址请求消息后， 通过查找地址表获取新加入节点的邻居节点地址以及尚未被分配的地址信息，并 采用上述的地址映射方法，按照节点地址的逻辑距离，从尚未被分配的地址中选 取新节点的地址。

当有社区中的节点要离开网络时，该节点向中心节点发送离开报告消息， 通知中心节点自己的离开，中心节点则根据收到的消息查找地址表，并删除其记 录。如图6所示为社区号为[11]的社区动态地址分配具体实现过程的示例，节点 地址的后三位是节点号。初始时，网络中有N_A(11000)、N_B(11010)、N_C(11100) 三个节点，其中节点N_A为中心节点，则中心节点N_A的初始化地址表为图6(a) 所示；有一个节点N_D向中心节点N_A发送地址请求消息，希望在节点N_B附近加入 网络，当收到节点N_D的地址请求消息时，中心节点N_A查找地址表可以发现距离 节点N_B的地址(11010)最近的两个地址(11001)和(11011)都尚未被分配， 因此随机选择其中一个地址(11011)分配给节点N_B，并更新地址表，如图6(b) 所示；当节点N_C离开网络时，它向中心节点N_A发送离开报告消息，中心节点N_A收到消息后，查找地址表，删除节点N_C的记录完成地址表更新，如图6(c)所 示。这种方式的好处是节约节点的内存资源，减小算法的空间复杂度。

为了避免节点离开网络时未通知中心节点或者中心节点没有成功接收到通 知消息的情况发生，中心节点每隔一定的时间向社区内所有的节点广播一个确认 信息，节点收到确认信息后，都需给中心节点回复一个信息，中心节点则根据回 复信息来更新地址表。