UASN 中改进的锚点定位报文传输方案研究

徐向艺，王启明

UASN 中改进的锚点定位报文传输方案研究

徐向艺，王启明

定位问题是水下声学传感器网络的一个关键问题，如果节点采集到的数据没有附上时间和测量位置便没有意义。针对现有定位算法在报文传输效率方面的不足，文中提出了一种改进的定位报文传输方案。首先，已知锚点的相对位置及其最大传输范围后，分析了定位时的无冲突报文传输条件，然后，定义了定位任务时间最小化问题，并证明该问题可以获得最优解。在此基础上，提出了两种基于调度的低复杂度求解算法。最后，通过多次仿真验证了所提出的算法的准最优性能及相对其他当前算法的优越性。

水下声学传感器网络；定位；锚点；报文传输；最优解

0 引言

为了满足水下应用的需要，水下声学传感器网络[1]（UASN）负责测量水温、化学物密度、海床形状等参数。如果这些数据没有附上时间和测量位置便没有意义，所以定位问题是UASN的重要问题，促使人们对水下定位展开大量研究[2,3]。虽然可以在定位时使用当前的无线传感器网络的MAC协议和算法，但是鉴于UASN的独特属性，比如传输延时较长、数据速率较低、传输损耗较大，导致使用当前无线传感器网络的MAC协议和算法的效率不高[4,5]。

梁玥等[6]针对UASN中锚节点稀少的问题，给出了一种分布式的水下节点自定位算法。为配合定位算法的实现，提出了一种分布式的并发数据传播算法，并针对该数据传播算法中存在的通信冲突问题，给出了冲突解决策略。文献[7]提出了有序调度协议（OCSMA）来广播锚点报文。该协议中有一个协调器根据关于锚点相对位置的完整信息来确定传输序列，然后向锚点通知所生成的序列。此时，锚点根据指定序列逐个进行报文传输。然而，该协议对定位任务来说并不是最优协议，因为它不支持在网络中同时传输数据。为了克服这一问题，文献[8]提出了一种单跳多对多广播传输调度协议（AAB-MAC）。该协议的目标是在保证不发生冲突的前提下尽量减小多对多传输周期。虽然AAB-MAC优于OCSMA，但它无法用于定位任务，一方面是因为我们不知道所有水下传感器节点的位置，另一方面是因为只对锚点使用AAB-MAC协议会导致传感器节点冲突。当前还有其他多种基于调度的水下网络MAC协议[9,10]。但是，它们着眼于单播报文交换，没有考虑基于定位信标的无冲突广播，因此，不适用于水下网络定位任务。

在本文中，我们研究了锚点定位报文的调度问题。利用锚点的位置信息及传输范围信息来尽量降低定位任务的时间。所有锚点传输完各自报文后，定位过程才算结束。每个锚点报文中的信息包括锚点ID、锚点位置及报文传输时间。我们探讨了定位任务时间最小化问题，并证明该问题可以获得最优解。然后，提出了两种基于调度的低复杂度求解算法（L-MACs）。最后，通过多次仿真验证了本文算法的准最优性能及相对其他当前算法的优越性。

1 网络模型

假设水下传感器网络有N个位于水面的锚点（如果位置信息已知，则可位于任何地方），且最大传输范围为R米，在锚点的覆盖范围内有M个水下传感器节点。假设水面锚点配备了GPS设备、无线电（或卫星）和声学调制解调器。此外，融合中心通过无线调制解调器可以收集锚点信息。另一方面，没有关于水下传感器节点位置的先验信息，且传感器可能位于监测区域的任何位置。融合中心负责对锚点的定位报文传输进行调度，且每个报文的时间为tp。我们的目标是使定位时间最小化，并避免任何水下传感器节点在接收报文时发生冲突。为此，融合中w心在每个锚点传输报文前为每个锚点i设置一个等待时间i。

为了避免任何潜在的报文冲突，我们必须解决的一个问题是使最大等待时间最小化。如果一个传感器节点有两个甚至更多个传输报文互相重叠，则我们认为发生冲突。但是，因为传感器节点可能位于媒介中的任何位置，所以，来自锚点的传输报文可能在两个锚点传输范围的相交区域任一位置发生冲突。此时，即使两个锚点没有位于声学传输范围内，它们也有可能在网络中发生冲突，如图1所示：

图1 两个高危冲突锚点的示意图

为了避免冲突问题，我们引入无冲突锚点概念。简单地讲，如果两个锚点的距离小于最大传输范围的两倍，则称这两个锚点为冲突高发相邻锚点，发生冲突的概率较大。在下一小节，我们将证明如何改变等待时间以避免发生锚点冲突问题。

1.1 无冲突锚点

条件1：当两个锚点间的距离大于2R 时，那么无论需要等待多少时间，它们的传输报文均不会发生冲突，因为它们的传输范围没有相交区域。我们将这两个锚点称为严格距离相关无冲突节点。

条件2：假设水下媒介的声速为c 。如果两个等待时间之差为则无论节点间距如何，两个节点的传输报文也不会发生冲突。我们将这两个锚点称为严格时间相关无冲突节点。

图2 当时的无冲突锚点

可以发现，阴影区域被第1个和第2个锚点覆盖且没有任何冲突。当时本条件成立，否则属于条件2情况。可以推断，如果则可保证锚点不发生冲突的最小值为，如公式（1）：

总体来说，wi未必大于wj的等待时间已知时为了保证定位报文不发生传输冲突，则wi必须在下述边界之外：

图3时的无冲突锚点

如上文所述，wi未必大于wj，那么当锚点j的等待时间已知时为了保证定位报文不发生传输冲突，则wi必须在下述边界之外，如公式（4）：

在明确了无冲突报文传输的相关条件后，我们将优化问题定义，如公式（5）：

公式（5）中，（1）表示我们无法在负数时间传输报文，

（2）表示条件1-4的融合。

我们从条件3和4中可以发现，为了保证无冲突报文传输，设置一个锚点的等待时间后将会对相邻无冲突锚点的等待时间带来约束。这些约束不仅与锚点报文传输之后的时间有关，还与锚点报文传输之前的时间有关。这一点对于确定公式（5）的最优解非常重要。在下一小节，我们给出如何利用时分多址（TDMA）系统定义公式（5）中的问题。

1.2 TDMA系统下的问题定义

2 最优解

本节首先讨论如何获得时隙方法的最优解，然后以此为基础，阐述如何对该最优解进行拓展以确定本文问题的最优解。

如前所述，以严格距离相关无冲突锚点和严格时间相关无冲突锚点概念为基础的时隙调度是NP难题，可看成是混合整数线性规划问题（MILP）。其中，最优解（可能唯一）存在于N!个可能解中，通过穷尽搜索可以获得。已知锚点序列后，我们给出如何将锚点分配给最小数量的时隙可以避免冲突。以此已知序列为基础，我们从第1个锚点开始，将其分配给第1个时隙。然后，我们移到第2个锚点，将其分配给考虑了先前调度的锚点之后也不会导致冲突的最早时隙。然后，重复相同步骤，直到最后一个锚点调度完毕。最后，我们计算使用时隙的数量，在所有N!个可能序列中，我们选择时隙数量最少的序列。

为了获得本文问题的最优解，我们遵守相同的步骤。然而，此时我们需要确定锚点无法传输报文的时间长度（考虑了先前被调度的锚点后可能导致的冲突）。如果已知有序序列后，一个锚点想要传输报文，则它在知道了先前被调度锚点的等待时间后计算可用于传输报文且不会导致冲突的最早可用时间段（见条件1、3、4）。重复这一步骤，直到最后一个锚点被调度完。最后，比较所有锚占序列（N!个可能序列）的最大等待时间最小的最优次序。我们将可以求解公式（5）优化函数的所有算法称为L-MAC算法。

3 本文算法

最优解的复杂度（不使用启发式策略）为N!，当锚点数量较大时可行性很低。在本节中，我们提出复杂度分别为的两种启发式算法，可用于不同场景。

3.1 L-MAC-IS

L-MAC-IS算法的步骤见算法1。在该算法中，所有等待时间在初始步骤中设置为0。算法在开始时调度一个经过预先设置的随机锚点（比如第I 个锚点）。因此，该锚点的等待时间设置为0。当锚点的等待时间设置完毕后，将从调度任务中删除。以此固定的等待时间为基础，检测先前被选择的锚点的无冲突相邻锚点，改变它们的等待时间，以保证网络中不会发生冲突（基于条件1-4的无冲突锚点）。然后，从未经过调度的锚点中选择等待时间最短的锚点，重复上述步骤，直到所有锚点的等待时间均被确定为止。有可能有两个或更多个锚点的最小等待时间相同。此时，我们选择序号最小的锚点。

算法1：L-MAC-IS :从第I 个锚点开始将所有等待时间设置为0：对

End for

3.2 最优启动器算法

最优启动器算法(L-MAC-BS)是L-MAC-IS算法的一种拓展。在L-MAC-BS中，我们对所有锚点(I=1toN)运行L-MAC-IS，选择可使总体调度时间最小化的锚点（最优启动器）。该算法的步骤见算法2：

算法2：L-MAC-BS :从最优锚点开始

End for

4 性能评估

本节评估本文算法的性能，并与最优解做比较。为了验证本文算法的优越性，我们还将其与OCSMA等当前水下MAC协议及传统的时隙方法做比较。在OCSMA中不允许报文并发传输，只有前一锚点传输完毕后，后一锚点才能传输。可以推测，如果每个锚点在所有其他锚点的声学传输范围内，则最优OCSMA协议便是定位时间最小化问题的最优解。寻找OCSMA的最优解是个NP难题[12]。因此，我们针对该算法再次使用首个最优启动器概念，并将其性能与本文算法做比较。每个点的计算，均是103次独立蒙特卡洛运行结果的均值，如图4所示：

图4 平均报文传输时间与锚点数量的变化情况

此外，定位报文的长度为50 ms，（使用声学调制解调器且数据率为1kbps时有50位），足以传输锚点ID、位置和传输时间等信息。

图5 平均报文传输时间与锚点最大传输范围的变化情况

L-MAC-BS、L-MAC-1S（首先选择序号为1的锚点）和最优解的性能非常接近；如果应用场合对复杂度要求较高，则可选择L-MAC-1S。由于比较费时，所以对其余仿真结果我们没有计算最优解的性能。

图5给出了区域范围确定后，最大传输范围对tavg的影响。可以看出，当R 增加时，严格距离相关无冲突锚点的数量将会下降，于是报文同时传输的概率下降，tavg上升。当网络完全连通时，tavg的上升趋势停止，如前文预测，此时OCSMA的性能与本文算法相近。

如图6所示：

图6 算法性能与网络规模的变化情况

我们给出了算法和网络规模的变化情况。此时，当作用区域的尺寸增加时，锚点的数量也将上升，以保证单位面积的锚点数量不变。同时，当网络面积增大时，更多节点成为严格距离相关无冲突节点的概率下降，节点的等待时间变长。然而，当网络增大时，高危冲突相邻节点的平均数量趋于一个固定值，于是时隙算法和本文算法的性能达到饱和。相反，OCSMA的性能下降，原因是锚点数量上升，总体定位时间也将上升。

5 总结

本文定义了水下传感器网络的定位报文调度问题。此外，提出两种低复杂度算法，以实现定位任务的时间最小化。我们证明本文算法的性能达到准最优水平，且远优于TDMA和OCSMA等其他当前算法。下一步，我们将研究大部分水下节点不在锚点覆盖范围内时的定位问题。这类网络的最优MAC协议可以看成是本文情况的一种拓展。

[1] 郭忠文,罗汉江,洪锋.水下无线传感器网络的研究进展[J].计算机研究与发展,2010,47(3):377-389.

[2] 魏先民.基于多面体质心算法的水下传感器网络定位[J].计算机科学,2012,39(5):102-105.

[3] Han G, Jiang J, Shu L, et al. Localization algorithms of underwater wireless sensor networks: A survey [J]. Sensors, 2012, 12(2): 2026-2061.

[4] 周异,陈剑波,陈凯,等.基于移动信标的大规模水下传感器网络节点定位[J].计算机应用与软件,2011,28(10): 55-57.

[5] 王彪,李宇,黄海宁.水声传感器网络目标协同定位方法研究[J].系统仿真学报,2013,12 (19): 6174-6177.

[6] 梁玥,刘忠,夏清涛.水下声学传感器网络节点定位算法及自组织过程研究[J].传感技术学报,2014,24(3): 402-406.

[7] Van Kleunen W, Meratnia N, Havinga P J M. Scheduled MAC in beacon overlay networks for underwater localization and time-synchronization[C]. Proceedings of the Sixth ACM International Workshop on Underwater Networks. ACM, 2014: 6-13.

[8] Soonchul P, Jaesung L I M. A Parallel Transmission Scheme for All-to-All Broadcast in Underwater Sensor Networks [J]. IEICE transactions on communications, 2010, 93(9): 2309-2315.

[9] Hsu C C, Lai K F, and Chou C F, et al. ST-MAC: Spatial-temporal Mac scheduling for underwater sensor networks[C]. INFOCOM 2009,IEEE. IEEE,2009: 1827-1835.

[10] Kredo K, Djukic P, Mohapatra P. STUMP: Exploiting position diversity in the staggered TDMA underwater MAC protocol[C]. INFOCOM 2009, IEEE. IEEE, 2009: 2961-2965.

[11] Ergen S C, Varaiya P. TDMA scheduling algorithms for wireless sensor networks [J]. Wireless Networks, 2014, 16(4): 985-997.

[12] Chen Y J, Wang H L. Ordered CSMA: a collision-free MAC protocol for underwater acoustic networks[C]. OCEANS 2007. IEEE, 2007: 1-6.

TP393

A

2015.01.20）

1007-757X(2015)07-0014-05

国家自然科学基金（NU1204611）；河南省自然科学基金（132300410278）

徐向艺（1979-），女（汉族），河南平顶山人，平顶山学院，软件学院，讲师，硕士，研究方向：智能算法、网络安全，平顶山，467002

王启明（1980-），男，河南鲁山人，平顶山学院，软件学院，讲师，硕士，研究方向：软件工程、物联网，平顶山，467002