分层结构方法的优化探析

参考文献（Jiang and Wu，2008）提出了一种基于哈密顿回路的分层传感器重定位协议。实际上，它是基于本地区域分层位置服务的一种变形（第8章已进行了描述）。在该算法中，传感器具有相同的通信半径r_c和感知半径r_s（r_s=r_c），且感知区域被均匀划分为多个r×r网格，其中c（该r支持每个节点与相邻网格中的节点直接进行通信）。采用这种划分方法，只要每个网格中存在一个节点，网络连通性和全覆盖就能得到保持。

在单元网格中，选择一个节点作为网格头，而其他节点为网格成员，且被认为是冗余的。4个相邻单元网格形成一个逆时针方向的1级有向哈密顿回路，且选择其中一个单元网格作为哈密顿回路的“眼睛”。眼睛网格头沿着回路，采集4个单元网格中冗余节点的存在信息。4个相邻的1级哈密顿回路的“眼睛”进而形成一个2级有向哈密顿回路，并共享信息。该哈密顿回路以递归方式执行，直到形成一个覆盖整个感知区域、由4个（k-1）级哈密顿回路的“眼睛”构建的k级有向哈密顿回路为止。单元网格头对单元网格中冗余节点的任何变化进行监视，并采集变化信息，然后在分层哈密顿回路结构中向上更新。

当网格头u发现所在1级有向哈密顿回路方向中的相邻网格为空时，它启动一次级别内修复过程，来修复检测到的空穴。它选择网格中的一个冗余节点，运动到空穴网格。如果没有可用的局部冗余节点，则u自身将运动到空穴网格处。在运动前，它向所在1级有向哈密顿回路的前一个网格头v发送一条通知。接到通知后，v为网格u重复上述过程，导致转移节点迁移。如果u所在1级有向哈密顿回路眼睛的头w在其受控区内（接到通知后），发现缺少用于请求局部空穴修复的冗余节点，它将启动一次级别间修复过程。(www.xing528.com)

在级别间修复过程中，w沿着其所在的2级哈密顿回路，搜索一个冗余节点，然后继续执行，直到在第i（i≤k）级眼睛处找到一个冗余节点。然后，针对冗余节点的定位过程在第i级眼睛处启动。它将沿着相应的第i级回路进行，到达在其受控域内至少有下一个冗余节点的第（i-1）级眼睛。该过程继续进行，直至到达单元网格。然后，冗余节点将采用转移方式进行迁移，沿着上述级别间搜索和下行定位过程中构建的路径，来填补检测到的空穴网格。