回溯部署方法详解

针对有界ROI，参考文献（Fletcher et al.，2009）提出了一种基于回溯的局部传感器部署（BTD）方法。执行器携带传感器，随机分布在ROI中。它们知道自身的位置，能够检测物理障碍、ROI边界和早期部署的传感器。为4个地理方向（即北、西、南、东）分配给不同的等级。如果某个方向处于阻塞状态（被障碍物、ROI边界或传感器），则执行器选择朝下一个最高等级的方向运动。在运动过程中，它在合适的位置（服从理想网络拓扑，如方格或TT）撒布传感器。与LRV（Batalin and Sukhatme，2005）和SLD方法（Chang et al.，2007）不同，BTD在有限时间内终止，实现ROI上的全覆盖。其细节描述如下。

空点是指传感器预计被撒布的地理点。我们称传感器与某个空点相邻，如果它在预期网络拓扑中是这样的话。根据传感器的邻域状态，按照如下规则，为每个传感器动态分配一种颜色：如果存在一个相邻空点，则为传感器分配“白色”，否则为传感器分配“黑色”。后一个传感器（或前一个传感器）是在它之后（或前）同一执行器立即撒布的传感器。每个传感器存储一个前向指针和后向指针。前者指向前一个传感器的位置。如果前一个传感器是白色的，则后向指针指向后一个传感器的位置，否则，后向指针指向其前一个传感器后向指针指向的位置。换句话说，它指向沿着撒布执行器后向路径的第一个白色传感器。如果传感器没有后一个传感器（或前一个传感器），则将其前向（或后向）指针设置为0。前向指针和后向指针共同作为导航工具，且支持执行器回溯相互的轨迹。

执行器有与众不同的ID。它们将其ID和递增序列号，通知给每个它所撒布的传感器。同一执行器撒布的传感器具有不同的序列号，而那些不同执行器撒布的传感器可能不是这样。通过采用周期性“问候”消息，传感器与其邻居交换诸如位置、撒布执行器的ID、序列号、颜色和后向指针等局部信息。因此，颜色和前向/后向指针设置都是以局部方式定义的。图10-4给出了在一个ROI内的BTD执行期间，4个瞬间的这些行为配置结果。在该实例中，两个执行器a和b从不同位置A和B出发，采用方格拓扑来配置传感器。它们按照西>东>北>南的优先级次序运动。它们当前位置用小三角形来标记，它们正在移动的目标用粗箭头线表示。传感器的后向和前向指针用细直箭头线和弯箭头线来表示。

图10-4 BTD中的盲端和回溯(https://www.xing528.com)

位于执行器当前位置的传感器称为执行器的当前传感器。如果所有4个移动方向都是阻塞的，则我们称执行器到达盲端。在这种情形中，执行器沿着后向指针链从其当前传感器回溯，回访上一个白色传感器，寻找其相邻的空点（未覆盖区域的入口），从该点重新开始ROI搜索和传感器撒布。如果执行器在当前传感器上，无法找到一个非零后向指针，则它将检查邻域内是否存在一个存储的后向指针。如果结论是否定的，则它将终止操作；否则，它沿着存储在具有最大序列号的相邻传感器处的后向指针运动。为了防止形成环路，需要进行随机选取。

当执行器正为白色传感器进行回溯时，我们称执行器正为该传感器服务。如果服务执行器数等于其相邻空点数，则我们认为传感器接受服务。在执行器开始为白色传感器服务之前，它向该传感器发送一条请求消息。只有当该请求被批准后，或者在一系列重试后，如果没有接收到回复，执行器才开始采取实际服务行动。执行器的传感器撒布行动可以改变附近白色传感器的颜色，颜色变化会沿着从传感器到其撒布执行器的前向指针链，触发后向指针的变化。由于网络异步性和信息传播延迟，执行器可能会运动到来自于盲端的黑色传感器。在这种情形中，执行器将到达另一个盲端。

图10-4给出了4个盲端的情况。在图10-4a中，执行器b到达了一个盲端，决定沿着当前传感器的后向指针，回溯到白色传感器。如图10-4b所示，当它到达目标时，白色传感器变成黑色，因为它唯一的相邻空点被执行器a所撒布的传感器占据。两个执行器都处于盲端情形中，它们决定沿着它们到第一个先前白色传感器的路径向后运动。之后，执行器到达图10-4中的另一个盲端。因为它无法在当前传感器上找到一个非零后向指针，所以它沿着存储在执行器a撒布的相邻传感器上的后向指针回溯。然后，执行器a也到达图10-4中的一个盲端，并执行回溯过程。

后向指针链路中的单个节点失效不会影响算法的执行。这是因为执行器将被引导至失效传感器所在的位置，并使用新传感器来代替它，然后执行器将恢复从失效节点的前一个传感器处，恢复存储在失效节点的后向指针。如果多个相邻传感器同时失效，就会出现一个感知空穴。同样，执行器将被引导至空穴区域。它将空穴看做是未覆盖区域，并在此撒布传感器。沿着空穴边界存储的后向指针，可以识别位于空穴区外的任意白色传感器，空穴被修复后，执行器将沿着这些指针来部署传感器。