如何检测网络临界节点与链路？

在传感器与执行器网络中，某些节点或链路失效，如果导致网络生成几个分区，对于从区域中采集数据或在传感器上执行特定操作来说可能是致命的。但是，可以预见的是，网络在分区之前，往往表现出一些临界连通性。及时认识到这些特性，可能会支持执行一些数据或业务复制，这样在分区发生后，网络还可以继续工作。这种检测也可用于部署时间（如在确定公共通信半径时）以确保没有这种临界节点或链路存在，也就是说，网络是双连通的。可以考虑在两种方法中加入容错。我们下面讨论检测临界链路和节点的一些思路。

比较著名的是基于全局知识来检测临界节点和链路的算法。但是，它们在传感器网络中的应用受到限制，因为它要求每个实体都知道整个拓扑的信息，这意味着算法是不可扩展的，且拓扑变化和系统反应之间存在着延迟。因此，以局部和分布式方式来检测临界链路和/或节点似乎更为可取，即使可能会犯一些错误，导致对连通性产生更为“悲观的看法”（将某个元素看做是临界，但实际上并非如此）。

在全局环境中，我们称某个节点或链路是临界的，如果它断开网络，即如果将它分割到几个连通组件中。临界节点和链路的定义在局部环境中需要稍作修改。正如参考文献（Jorgic et al.，2004）中介绍的，如果它从p跳邻居的子图断开，则称该节点是局部临界的。在链路的情况下，考虑了几种定义。该论文中提到了3种定义，基于所采用的看局部连通性的方法。这些方法如图7-6所示。第一种方法包含看两个端点的p跳邻居以及看是否有些邻居是公共的（图7-6a）。第二种方法是在测试链路的两端启动面遍历，来看看能否在两跳之前到达另一端的点（图7-6b）。最后，如果其端点本身是临界的，且该信息当前处于可用状态，则也可以确定链路是临界的（图7-6c）。

图7-6 临界链路

（此处指的是（AB）的局部检测。针对每种方法，如果标题公式成立，则认为该链路是临界的）(www.xing528.com)

正如参考文献（Jorgic et al.，2004）所讨论的，根据位置信息对于节点来说是否可用，可以研究每种定义的变形。我们考虑图7-7中的简单实例，其中节点A和B必须基于单跳邻居信息，来确定它们的公共链路是不是临界的。如果C和D各自的位置是已知的，则不需要附加信息，就可以确定在它们之间是否存在一条链路的事实，而仅使用拓扑信息是不可能确定的。显而易见，这种基于位置的推导采用不存在障碍物的UDG模型。作者将这两种变形表示为k-top临界和k-pos临界。

采用随机UDG的实验显示，全局和局部决策之间存在着高度相关性。唯一的区别是当备选路由存在，但相对较长时。关键是真正的临界要素同样可以被检测到，任何错误的判断只在过度谨慎（为防止反应性复制）或连通性轻微过度（以防止链路选择）中产生。

图7-7 位置信息可用性对临界检测的影响

正如参考文献（Jorgic et al.，2007）中所提到的，可以将这些概念推广到网络的临界k连通性情形。在本文的第一个协议中，每个节点通过验证每个p跳邻居度数（邻居数）是否至少为k，来做出临界性决策。第二个协议也验证给定节点的p跳邻居子图是否为k连通的。第3个协议也可以验证该子图是否包含任何临界节点。