S-TDMA传感器网络监测河羽毛的最佳公平计划

摘要

水下无线传感器网络（UWSNS）是一个有前途的技术，可以实时向环境数据提供海洋记录器。用于监测河口的合适的网络拓扑通过串组合在一起到汇聚节点形成。该网络可以被理解为定向图。可以在UWSN中使用许多MAC技术，但是Spatial-TDMA是针对固定网络的。在本文中，在理想的同步和传输误差条件下提出了一种获得最佳公平帧的调度过程。主要目的是通过重叠节点的传输来找到理论最大吞吐量，同时保持来自每个传感器的平衡接收数据速率，无论其在网络中的位置如何。该过程搜索网络图的兼容性矩阵的所有派系，并解决多向量箱包装（MVBP）问题。这项工作解决了优化问题，并为最小帧长和最大可实现的吞吐量提供分析和数值结果。

1.介绍

河口和三角洲的河流沉积物羽流对水质和环境的影响非常重要。用于监测近岸环境的技术可分为两大类:远程监测和原位监测。用于遥感的卫星装置(AVHR辐射计[1]，来自Modis-Aqua的图像[2)或无人驾驶飞行器[3.已被使用。现场测量可由水下传感器(即河道漂流器)进行[4或视频遥感[5]）。水下无线传感器网络（UWSNS）是海洋学中非常有前途和方便的仪器，特别是对于污染监测和海上勘探[6］．由于洋流和风的影响，沉积物羽流可能呈现出不同的模式。数字1介绍了UWSN的可能部署，旨在覆盖感兴趣的地区。网络中有两种类型的节点:传感器节点和汇聚节点。汇聚节点从传感器节点收集数据，作为网络网关。浅水区的声波信道非常危险。因此，选择一种高效的MAC协议对UWSN的设计至关重要[7］．从传感器到汇聚节点有两种可能的多跳传输机制:广播或点对点。后者是当前工作的选择。关于信道划分协议和随机访问协议的选择[8，9，时分多路复用(TDM)是首选的技术，因为它的简单和功率效率。STDMA (Spatial time division Multiple Access)是一种无冲突的多跳信道接入协议。10，在目前的工作中使用。

由于所有节点位置在数据采集方面同样重要，因此传输公平[11是一个调度目标。在这个分析中，公平是指所有节点在长期内传输相同数量的自己的数据，而不管它们与汇聚节点的距离如何。

本文将分析一个单sink网络。考虑了两个不同的网关位置，它将显示其位置如何对网络吞吐量有强大的影响。其他作者之前的工作是处理STDMA网络中的公平调度问题。Wang等人提出了一种调度算法，但他们强调的是自适应调度而不是最短帧[12］．关于UWSN，Diamant和Lutz提出了Ad Hoc UWSN的STDMA协议，其中考虑公平但未统一实现[13］．Chitre等人证明了随机网络的最优调度是周期性的，并提出了一种计算效率高的算法，可以找到好的调度[14[虽然我们的工作呈现了一种新的过程，但是当众知节点的位置时发现最佳调度。肖等人。还提出了一种在TDMA网络中找到最佳调度的算法，但仅在UWSNS中用于线性（单行）拓扑[15］．在拓扑结构遵循河口形状的网络中，我们的程序确定了饱和负荷情况下(即传感器节点总是有数据要传输)的最优公平调度。给出了帧长解析表达式和吞吐量的数值计算结果。

2.网络描述和调度

在深入分析STDMA网络调度之前，需要考虑一些方面。在网络拓扑中如图所示1 (b)节点位于等边三角形网格的顶点，它们是静止的。两个可能的网关位置如图所示2:入口在角落和中心。考虑这两个位置的主要原因是，它们是网络部署的性能和成本的两种限制情况。如果选择一个有中心网关的网络，由于网关到海岸的距离更大，因此获得最大吞吐量的代价更高。

随着这个词表示，羽流具有大羽毛的形状;也就是说，它占地面积超过宽，如图所示1(一)．为了适应这个感兴趣的领域，所选的网络拓扑由三个或六个(取决于网关位置)到网关的字符串组成。数字2还显示了13节点网络(12个传感器节点和一个网关)中每个节点的吞吐量。由于传输功率控制，相邻节点之间处于传输范围内，非相邻节点不在传输范围内[15］．传输模式是单纯x;也就是说，发送的节点不会同时接收，反之亦然。在初始同步阶段之后，转发表（由图中的箭头显示）2）将被设置，并将保持静止。

传感器获取的数据量使得每个节点总是有一个准备传输的数据包(饱和负载状态)。时间被分成同样长的时间段。在考虑时隙时，考虑了声波的长传播延迟和相关的时空不确定性，时隙不仅包括传播时间，还包括传播时间和保护时间。当一个节点传输时，它以一个恒定的二进制速率进行:通道数据速率，，等于所有节点。公平帧被定义为所有节点成功地向网关发送一个且只有一个自己的数据包所需的槽集。因此，网络操作是周期性的，周期就是帧的持续时间。为了尽量缩短帧长，允许同时传输。这就是空间时分多址的好处[10］．

TDMA调度是将插槽分配给节点以找到合适的周期帧。在TDMA调度中，可能是两种类型的分配：面向节点[16]及面向链接[17］．在声学网络中，当传感器(投影仪和水听器)没有方向性时，建议采用面向节点的分配方法。STDMA调度的第一步是确定兼容节点，即那些可以同时传输而不会引起任何内部网干扰的节点。有两种可能的传输不兼容性[17]：当节点在同一字符串中的邻居发送时，会发生1型1。当节点同时从两个或更多不同的发送节点接收时，发生类型2。计划将应对网络中的不兼容性。STDMA调度的下一步是找到最短的公平框架。这需要在两个约束下解决优化问题：（i）只能在相同的插槽中规划兼容节点，并且每个节点的传输数必须满足网络中的公平操作。

3.公平框架优化

本节详细介绍所提出的寻找最优公平帧的算法。让是传感器节点的数量（标记为；节点1是网关)，令为单个节点的吞吐量，让为节点的聚合吞吐量，即节点收集的数据导致的吞吐量加上从上游节点接收的数据并按节点转发．一个框架是一组特殊的时隙，每个时隙可能包含兼容节点的同时传输。为了在网络中设置公平行为，网关应该完全收到从网络的每个节点到帧的末尾。该约束强制了许多传输对于每一个节点在由集合给出的坐标系中．例如，在图中2(一个)，．寻找最短的公平框架的过程包括两个步骤:(A)寻找所有兼容节点集和(B)制定并求解组合优化问题以寻找最短的公平框架。第三步，去除多余的传输，是一个谨慎的做法，以避免过载的节点更接近网关。

３.１.兼容的节点

让是网络图，在哪里是节点集。主要的是（）， 和是一组边缘。如图所示2(一个)，在我们的网络中只有一条边离开结点，即所谓的边缘(因为传感器节点编号从2到)．当特定节点正在发送时，元素相容矩阵的［10]将为1，如果边(）可以同时发动，否则是0。为了启发兼容性矩阵的概念，图中提供了一个例子3.，我们可以注意到节点6没有兼容的节点()，因为节点6在传输时，（一世）节点3无法传输，因为它是从节点6接收，(2)由于节点6不在接收模式，邻居节点9无法发送，(3)邻居节点5和7会干扰节点3，(iv)邻居节点8和10无法传输，因为节点6传输将干扰节点5和7，(v)节点11、12和13(如图中“pn”所示)3（a）)无法传输，因为节点6会干扰节点8、9和10，（vi）节点2和4(标签“cn”在图中3（a）)无法传输，因为它们会干扰节点3。

网络中继方案可以用一个有向图表示。小团体的封面，，是图中最大团的集合。自然的数量未知先验。技术文献中有许多算法可以获得[18)找到．我们的首选算法是[19]，由于其效率和简单的实现。每个集团包含可以在没有冲突的情况下处于活动的边缘或一组边缘;显然，任何子集还满足了这一要求。图中的每个边缘包含在封面的至少一个Clique中，并且帧中的每次时隙都将包含盖子的一个Clique（或Clique的子集），这确保了该槽中的传输兼容性。

３．２．多向量装箱问题

我们需要找到最短的帧，其中每个槽包含一组边，或者说是边的子集，根据帧中的每个活动边缘的确切实例（以满足公平操作的要求），但是．这是一个多向量装箱(MVBP)问题[20.，其中箱子是时间槽，要打包的物品是向量，它们是或他们的子集。这是一个组合优化，广泛被认为是np完整问题[21］．我们统治了本MVBP问题的一般配方，并获得了 输出变量在哪里 ：1如果时间插槽使用或0否则; :该节点的次数分配给时隙(二进制的，因为一个节点只能在一个槽中传输一次); ：最短框架的长度。

我们帧搜索问题的约束是 ： 需求节点,对于公平的框架; :传感器节点数(） （节点2等）; :总人数(兼容传输:和子集）; :节点重量在这一点维度。每个向量代表了集团；如果节点是元素或0否则为0; ：能力维度。在我们的案件中，会是人数最多的小集团吗，

重要的是要注意每个子集集团被分配给不同的向量．例如，在Figure中3.,每一个将有组件。最大的clique是和三个创建向量:，意思是节点3（)及节点12 (）被允许独自或同时传输（)．

找到变速器的最佳调度在(1) - (5)，一种基于弧流图公式的MVBP问题求解算法[22),使用。

3.3。多余的传输

(2）意味着传输的需求（）可能超过初始集合．工作[22]所以，否则，MVBP求解器算法可以排除其他最佳解决方案。在我们的情况下，需求应该实现完全因为网络期望的公平行为。如果超过这个值，会带来两方面的不便:(1)可能出现流量瓶颈，因为额外的数据无法以帧的形式发送到网关;(2)不必要的传输造成能量浪费，因为节点消耗的能量是uwsn中的一个关键参数。最简单的解决方案是去除帧内多余的传输。

4.结果

为了简单起见，我们假设STDMA协议是理想的(无错误信道)，并在这些情况下计算了网络的性能。在一个真实的信道中，数据包的错误率必须考虑在内。长传播延迟表明首选的错误检测和校正技术是FEC (Forward error correction)。在这种情况下，吞吐量减少了一个等于FEC开销冗余因子的因子，但最优的公平调度保持不变。

前一节中描述的过程已被用于不同尺寸的网络，以获得最短的公平框架。框架长度，如图所示4，不能知道先验，因为问题是NP-Tress。我们已经分析了多达42个节点的网络，并使用多项式拟合算法来查找分析表达式，这在表格中显示1．这些结果可以帮助设计一个网络，因为它们允许计算从每个节点获得一个完整数据包所需的时间下限。值得注意的是，当网关位于中心时，帧长总是等于传感器的数量()．这意味着它的调度具有最短的长度。

框架中的传输数量，，是关于能量消耗的重要人物。它只取决于集合．当网络有三个或六个分支时是三倍之三，最佳公平框架中的传输次数遵循二次法律，给予 其中“mod”表示模运算。这些结果如图所示5．值得注意的是，每个节点的平均传输数量，，跟随线性法律．

标准化吞吐量定义为通过网关的二进制数据速率和通道数据速率之间的比率，．在本例中，这个数字可以通过传感器节点数与帧内槽位数的比值来计算，N/l．使用表中所示的最佳公平帧的长度1，标准化吞吐量如图所示6．可以看出，对于中心的网关中的网络，归一化吞吐量是1，并且可以获得超过12个传感器节点的网络中具有最多12个传感器节点的理想吞吐量的70％以上。我们认为，如果我们考虑到靠近岸边的门户更方便，这是一个可管理的性能损失。

结论

本文提出了一种确定具有公平性要求的STDMA UWSN最优帧的方法。网络由三到六根连接到网关的字符串组成。该调度程序采用两种算法，一种是在有向图中查找团，另一种是用MVBP问题求解器查找最短的帧。给出了最佳帧长的解析表达式。考虑了两个网关位置:在网络的中心/边缘。在理想条件下，前者性能最高，而后者在12个传感器节点的网络中达到最大标准化吞吐量的70%。

利益冲突

提交人声明没有关于本文的出版物的利益冲突。

参考文献

1. A. Marsouin，P. Le Borgne，G. Legendre，S.Péré和H. Roquet，“六年的Osi-Saf Metop-A AVHRR海面温度”环境遥感，卷。159，没有。3，pp。288-306,2015。查看在：出版商网站|谷歌学术
2. M. J. Devlin，C. Petus，E. Da Silva等，“水质和河流羽流监测在大堡礁：基于海洋颜色卫星数据的方法概述”遥感，第7卷，第5期10, pp. 12909-12941, 2015。查看在：出版商网站|谷歌学术
3. V. V. Klemas，“来自无人机的沿海和环境遥感:概述”，中国沿海研究杂志，卷。31，不。5，pp。1260-1267，2015。查看在：谷歌学术
4. M. Postacchini, L. R. Centurioni, L. Braasch, M. Brocchini，和D. Vicinanza，《来自河漂流者的波浪和水流的拉格朗日观测》，海洋工程学报号，第41卷。1, pp. 94-104, 2016。查看在：出版商网站|谷歌学术
5. D. Morichon，D.Dailloux，S.Aarninkhof和S. Abadie，“使用基于岸线的视频系统来为每小时监测风暴水羽毛（Adour River，Beishay），”中国沿海研究杂志，卷。24，不。4，pp。133-140,2008。查看在：出版商网站|谷歌学术
6. D.庞帕利和铜景，“水下传感器网络通信协议设计中的挑战”水下声学传感器网络， CRC出版社，美国佛罗里达州博卡拉顿，2010年。查看在：谷歌学术
7. I. F. Akyildiz, D. Pompili，和T. Melodia，“水声传感器网络:研究挑战”，特设网络，第3卷，第2期。3，页257-279,2005。查看在：出版商网站|谷歌学术
8. R. Otnes, A. Asterjadhi, P. Casari等，水声网络技术，施普林格，海德堡，德国，2012。
9. S. Shahabudeen, M. Chitre，和M. Motani，“水声网络的自适应多模媒体访问控制”，海洋工程学报第39卷第3期3, pp. 500-514, 2014。查看在：出版商网站|谷歌学术
10. R. Nelson和L. Kleinrock，《空间TDMA:无碰撞多跳信道接入协议》，IEEE通讯汇刊，卷。33，不。9，pp。934-944，1985。查看在：出版商网站|谷歌学术|Mathscinet.
11. J. Mo和J. Walrand，“公平的端到端基于窗口的拥塞控制”，网络上的IEEE / ACM事务，卷。8，不。5，pp。556-567，2000。查看在：出版商网站|谷歌学术
12. 王振宇，田军，“一种基于不可靠链路的无线传感器网络自适应TDMA调度算法”，国际通信系统杂志，卷。27，不。10，pp。1535-1552,2014。查看在：出版商网站|谷歌学术
13. R. Diamant和L. Lampe，“空间重用时分多访问广播ad hoc水下声学通信网络”海洋工程学报，卷。36，不。2，pp。172-185,2011。查看在：出版商网站|谷歌学术
14. M. Chitre, M. Motani，和S. Shahabudeen，“具有大传播延迟的网络吞吐量”，海洋工程学报，卷。37，不。4，pp。645-658,2012。查看在：出版商网站|谷歌学术
15. Y. Xiao，M.Peng，J.Gibson，G. G.谢，D.-z。DU，A. V.VASILAKOS，无线传感器网络和水下传感器网络中MAC协议的MAC协议的紧密性能界。IEEE移动计算汇刊，第11卷，第5期。10, pp. 1538-1554, 2012。查看在：出版商网站|谷歌学术
16. P. Björklund, P. Väbrand，和D. Yuan，“一种用于ad hoc网络空间时分多址调度的列生成方法”，特设网络，第2卷，第2期4，页405 - 418,2004。查看在：出版商网站|谷歌学术
17. 是。Chou和V. O. K. Li，“多彩色数据包无线网络中TDMA协议的插槽分配策略”IEEE计算机和通信协会第11届年会的诉讼程序（IEEE Infocom '92），卷。2，pp.710-716，佛罗伦萨，意大利，1992年5月。查看在：谷歌学术
18. E. R.哈利，《小团体列表算法的比较》国际建模、仿真与可视化方法会议论文集和国际算法数学与计算机科学会议论文集(MSV-AMCS '04)，卷。4，PP。2004年6月，涅夫斯拉斯维加斯433-438。查看在：谷歌学术
19. C. Bron和J. Kerbosch，《算法457:寻找无向图的所有团》，ACM的通信，第16卷，第5期。第9页575-577,1973。查看在：出版商网站|谷歌学术
20. B. pat - shamir和D. Rawitz，《多重选择的向量箱包装》离散应用数学号，第160卷。10-11, pp. 1591-1600, 2012。查看在：出版商网站|谷歌学术|Mathscinet.
21. M. R. Garyy and D. S. Johnson，计算机和棘手性，np完备性理论指南1979年，美国加州旧金山，弗里曼市。
22. F. Brandão和J. P. Pedroso，“Bin packing and related problems: general arc-flow formulation with graph compression，”Tech. rep DCC-2013-13, Faculdade de Ciências da Universidade do Porto，波尔图，葡萄牙，2013，http://www.optimization-online.org/DB_FILE/2013/10/4096.pdf．查看在：谷歌学术

版权

版权所有©2016 Miguel-Angel Luque-Nieto等人。这是一篇发布在知识共享署名许可协议如果正确引用了原始工作，则允许在任何媒体中的不受限制使用，分发和再现。