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

林奕水， 何震苇

(1. 广东农工商职业技术学院，广东 广州 510507；2. 中国电信股份有限公司 广东研究院，广东 广州 510507)



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

林奕水1， 何震苇2

(1. 广东农工商职业技术学院，广东 广州 510507；2. 中国电信股份有限公司 广东研究院，广东 广州 510507)

水下声学传感器网络具有传输延时较长、数据速率较低、传输损耗较大等特点，影响着现有定位算法的报文传输效率。针对水下声学传感器网络中现有定位算法在报文传输效率方面的不足，提出了一种改进的定位报文传输方案。首先，已知锚点的相对位置及其最大传输范围后，分析了定位时的无冲突报文传输条件，然后定义定位任务时间最小化问题，并证明该问题可以获得最优解。在此基础上，提出两种基于调度的低复杂度求解算法。最后，通过多次仿真实验来比较该改进算法与OCSMA等当前水下MAC协议及传统的时隙方法的性能，实验结果表明本文算法的性能达到准最优水平，且远优于TDMA和OCSMA等其他当前算法。

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

0 引 言

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

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

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

1 网络模型

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

为了避免任何潜在的报文冲突，我们必须解决的一个问题是使最大等待时间最小化。如果一个传感器节点有两个甚至更多个传输报文互相重叠，则认为发生冲突。但是因为传感器节点可能位于媒介中的任何位置，所以来自锚点的传输报文可能在2个锚点传输范围的相交区域任一位置发生冲突。此时，如图1所示，即使2个锚点没有位于声学传输范围内，它们也有可能在网络中发生冲突。为了避免冲突问题，引入无冲突锚点概念。简单地讲，如果两个锚点的距离小于最大传输范围的2倍，则称这2个锚点为冲突高发相邻锚点，发生冲突的概率较大。在下一小节，将证明如何改变等待时间以避免发生锚点冲突问题。

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

1.1 无冲突锚点

假设有两个锚点i和j，相距dij，等待时间分别为wi和wj且wi>wj。当它们满足如下三个条件时，则上述两个锚点无冲突：

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

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

(1)

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

(2a)

(2b)

图2 当R

条件4：如果wi-wj>tp+dij/c，则锚点i和j为无冲突锚点，图3为wi-wj最小值情形。当dij

(3)

图3 dij

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

(4a)

(4b)

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

s.t. (1)wi≥0,fori=1,2,…,N

(5)

其中，式(1)表示我们无法在负数时间传输报文；式(2)表示条件1～4的融合。

从条件3和4中可以发现，为了保证无冲突报文传输，设置一个锚点的等待时间后将会对相邻无冲突锚点的等待时间带来约束。这些约束不仅与锚点报文传输之后的时间有关，还与锚点报文传输之前的时间有关。这一点对于确定式(5)的最优解非常重要。

1.2 TDMA系统下的问题定义

在TDMA系统下，如每个时隙的时间长度设为ts=tp+R/c，则有R/c→0，于是式(5)优化函数等价为定位报文无冲突传输时使时隙数量最小化。因此，问题式(5)可建模为TDMA广播调度问题[14]。如文献[9]所示，用最小数量的时隙实现报文调度是NP难题。然而，R/c→0时广播问题的解是可实现定位任务最小化的最优解。当R/c≠0时，该解不是最优解，但仍然可以用于定位报文调度。把可以实现广播调度问题时隙数量最小化的最优和准最优算法称为时隙或TDMA算法。在无线传感器网络中，波速为光速，传输时间可以忽略，因此时隙算法性能较优。然而，水下通信的传输时延很大，有时甚至大于报文长度，对定位报文来说更是如此。此时，时隙算法的效率较低，需要开发其他算法。

2 最优解

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

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

3 本文算法

最优解的复杂度(不使用启发式策略)为N!，当锚点数量较大时可行性很低。现提出一种复杂度分别为N和N2的两种启发式算法，可用于不同场景。

3.1 L-MAC-IS

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

表1 L-MAC-IS算法

3.2 最优启动器算法

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

表2 L-MAC-BS算法

4 性能评估

本节评估本文算法的性能，并与最优解做比较。为了验证本文算法的优越性，还将其与OCSMA等当前水下MAC协议及传统的时隙方法做比较。在OCSMA中不允许报文并发传输，只有前一锚点传输完毕后，后一锚点才能传输。可以推测，如果每个锚点在所有其他锚点的声学传输范围内，则最优OCSMA协议便是定位时间最小化问题的最优解。寻找OCSMA的最优解是个NP难题[15]。因此，针对该算法再次使用首个最优启动器概念，并将其性能与本文算法做比较。下面图形中每个点的计算，均是103次独立蒙特卡洛运行结果的均值。此外，定位报文的长度为50 ms，(使用声学解调器且数据率为1 kb/s时有50 b)，足以传输锚点ID、位置和传输时间等信息。

图4中的方形区域有dx=dy=5c，且假设锚点均匀分布于该区域上。锚点的最大传输范围为2c。这里，增加锚点的数量，然后计算定位任务的平均时间，且定义tavg=E[wmax+tp]。如图4所示，L-MAC-BS、LMAC-1S(首先选择序号为1的锚点)和最优解的性能非常接近；如果应用场合对复杂度要求较高，则可选择L-MAC-1S。由于比较费时，所以对其余仿真结果我们没有计算最优解的性能。

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

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

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

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

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

5 结 语

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

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

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

[3] Han G, Jiang J, Shu L,etal. 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]. 系统仿真学报, 2009 (19): 6174-6177.

[6] 梁 玥, 刘 忠, 夏清涛. 水下声学传感器网络节点定位算法及自组织过程研究[J]. 传感技术学报, 2011, 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]//ACM, New York, 2011: 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,etal. 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] 田志辉，金志刚，王 颖. 基于可变长时隙机制的水下传感器网络MAC协议[J]. 计算机应用，2014， 34(7):1947-1950.

[12] 金志刚，苏毅珊，刘自鑫. 基于运动预测的水下传感器网络MAC协议[J]. 电子与信息学报，2013,35(3)：728-734.

[13] 洪 璐，洪 锋，李正宝. CT-TDMA: 水下传感器网络搞笑TDMA协议[J]. 通信学报，2012,33(2)：164-174.

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

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

Improved Localization Packets Transmission Scheme of the Anchors in UASN

LINYi-shui1,HEZhen-wei2

(1. Guangdong AIB Polytechnic College, Guangzhou 510507, China；2. Guangdong Research Institute of China Telecom Corporation Limited, Guangzhou 510507, China)

Underwater acoustic sensor network has characteristics of long transmission delay, lower data rate, high transmission loss. These characteristics affect the transmission efficiency of the existing positioning algorithm. Aiming at the deficiency, this paper proposes an improved localization packets transmission scheme of the anchor. After knowing the relative positions of the anchors and their maximum transmission range, we firstly analyze the collision free packet transmission conditions, and then define the positioning task time minimization problem, and prove that the optimal solutions can be obtained. On this basis, we propose two low complexity algorithms based on scheduling. Finally, several simulation experiments are conducted to compare the performance of the improved algorithm with the current underwater MAC protocol OCSMA and the traditional time slot method. Experimental results show that the performance of the proposed algorithm is quasi-optimal, and it is better than other current algorithms such as TDMA and OCSMA.

underwater acoustic sensor network; localization; anchor; packets transmission; optimal solution

2015-06-15

国家科技重大专项课题(2014ZX03002002)

林奕水(1980-)，男，广东汕头人，硕士，工程师，研究方向：水下传感器网络，数据收集。

Tel.：13710338768；E-mail: 44145735@qq.com

TP 391

A

1006-7167(2016)02-0089-05