[go: up one dir, main page]

CN111800200B - 一种水声网络并行通信的发送时间规划方法 - Google Patents

一种水声网络并行通信的发送时间规划方法 Download PDF

Info

Publication number
CN111800200B
CN111800200B CN202010540228.5A CN202010540228A CN111800200B CN 111800200 B CN111800200 B CN 111800200B CN 202010540228 A CN202010540228 A CN 202010540228A CN 111800200 B CN111800200 B CN 111800200B
Authority
CN
China
Prior art keywords
time
node
nodes
sending
source
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
CN202010540228.5A
Other languages
English (en)
Other versions
CN111800200A (zh
Inventor
张军
宁更新
冯义志
季飞
余华
陈芳炯
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
South China University of Technology SCUT
Original Assignee
South China University of Technology SCUT
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by South China University of Technology SCUT filed Critical South China University of Technology SCUT
Priority to CN202010540228.5A priority Critical patent/CN111800200B/zh
Publication of CN111800200A publication Critical patent/CN111800200A/zh
Application granted granted Critical
Publication of CN111800200B publication Critical patent/CN111800200B/zh
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04B—TRANSMISSION
    • H04B13/00—Transmission systems characterised by the medium used for transmission, not provided for in groups H04B3/00 - H04B11/00
    • H04B13/02—Transmission systems in which the medium consists of the earth or a large mass of water thereon, e.g. earth telegraphy
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W24/00—Supervisory, monitoring or testing arrangements
    • H04W24/02—Arrangements for optimising operational condition
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04W—WIRELESS COMMUNICATION NETWORKS
    • H04W72/00—Local resource management
    • H04W72/04—Wireless resource allocation
    • H04W72/044—Wireless resource allocation based on the type of the allocated resource
    • H04W72/0446—Resources in time domain, e.g. slots or frames

Landscapes

  • Engineering & Computer Science (AREA)
  • Computer Networks & Wireless Communication (AREA)
  • Signal Processing (AREA)
  • Data Exchanges In Wide-Area Networks (AREA)

Abstract

本发明公开了一种水声网络并行通信的发送时间规划方法，该方法首先将其他源节点已发送的包到达各自目的节点和当前目的节点的时刻映射到当前源节点的时间轴上，然后再对当前源节点发送包的时刻进行优化，可以消除现有方法对包到达顺序的约束，对节点的发送顺序进行自动调整，令发送时间规划的结果更合理，节点的发送时间表更紧凑，在更短时间内完成多个节点的传输，提高了并行通信的效率。本发明可以在优化过程中自动调整节点的发送顺序，无需大量搜索，减少了运算的复杂度。本发明可以广泛用于TDMA和基于握手的竞争式水声网络中。

Description

一种水声网络并行通信的发送时间规划方法
技术领域
本发明涉及水声通信技术领域，具体涉及一种水声网络并行通信的发送时间规划方法。
背景技术
水声网络是水下通信研究的重要课题，在水下勘探、水下石油开采、战术监控、污染监测、海啸预警、辅助导航、生态监控等方面有着广泛的用途。然而水声信道是一个复杂的时间-空间-频率变化、有限频带、长时延、大多普勒频移、强多途干扰和高噪声的信道，是自然界处理难度最大的无线通信信道之一，加上水下节点电池更换困难、位置容易漂移、水声换能器非全向辐射等因素的影响，使得水声网络的节点具有通信速率低、能量有限等特点，水声网络的链路具有时延大且动态变化、连接不稳定、双向非对称等特点，因此组建高性能的水声通信网络是一件困难且极具挑战性的工作。
由于水声信道可用的频带很窄，因此水下点对点声通信的速率受到很大限制，成为制约水声网络通信性能的主要原因之一。在点对点通信速率有限的情况下，增加节点间通信的并行度(即同时或并发通信的数量)无疑是提高网络通信性能的有效途径。在水声信道环境与水声网络应用场景下，主要存在着时域、空域和多信道三种并行通信的机会。时域上的并行通信机会是因水声网络中信息传播时延长带来的。由于水下声信号传播的速度只有1500m/s左右，因此处于不同位置的节点接收同一信号时常会存在较大的时延差异，如果能合理地利用这种时延差异，则可以实现多对节点互不干扰的并发通信。空域上的并行通信机会与水声网络的拓扑相关，网络中互在通信干扰范围外的节点可以并行地发送数据。多信道并行通信机会则是利用码分多址或频分多址技术在水下实现多条并行的通信信道。
时域的并行通信可以通过控制源节点的发送时间来实现，是水下最容易实现的并行通信方式之一。中国发明专利CN201410714302.5和中国发明专利CN201610697973.4分别提供了一种适用于全静态节点水声网络和包含运动节点水声网络的多节点并行通信方法，上述方法利用水声信道信息传播时延长的特点，通过合理规划节点的发送时间来实现多组节点在同一个传输周期内无冲突地并行传输数据，可以有效地提高信道的利用效率，减少通信的平均时延。中国发明专利CN201611159045.9中提供了一种节点发送顺序优化的竞争信道水声网络并行通信方法，该方法通过优化一个传输周期中多个节点的发送顺序及发送时间，能在实现节点数据无冲突并行传输的前提下，有效地减少一个传输周期所需的时间，从而提高信道利用效率。中国发明专利201710064153.6提供了一种节点发送时间和功率联合优化的水声网络通信方法，该方法通过控制节点的发送功率，在数据传输阶段将全连通网络转化为多个互不连通的子网，每个子网独立规划节点发送时间，子网间同时传输，子网内并发传输，能有效地减少一个传输周期所需的时间，提高信道利用效率，降低能耗。
上述方法均能利用水声信道时延长的特点来实现并行通信，有效提高现有基于握手的水下竞争MAC协议的性能，但这些方法在规划源节点的发送时间时，均假设：若节点i先于节点j发送包，则节点i的包将会先于节点j的包到达目的节点i和目的节点j。这个假设对包的到达顺序带来了额外的限制，在大多数情况下并不能得到最优的发送时间规划结果。
发明内容
本发明的目的是为了解决现有技术中的上述缺陷，提供一种水声网络并行通信的发送时间规划方法。该方法首先将其他源节点已发送的包到达各自目的节点和当前目的节点的时刻映射到当前源节点的时间轴上，然后再对当前源节点发送包的时刻进行优化，可以消除现有方法对包到达顺序的约束，对节点的发送顺序进行自动调整，令发送时间规划的结果更合理，从而提高水声网络并行通信的效率。本发明可以广泛应用于水声通信网、水声传感网等场合中。
本发明的目的可以通过采取如下技术方案达到：
一种水声网络并行通信的发送时间规划方法，该水声网络由多个节点构成，每个节点具有相同的时钟，每个节点保存一张记录所有节点间传播时延的表，其特征在于，在每个传输周期中采用以下步骤进行包的发送时间规划：
S1、每个源节点获取当前传输周期所有源节点及其相应的目的节点的列表，以及水声网络中所有源节点要发送包的时长；
S2、令Si＝(si,di)表示当前传输周期的第i对源节点和相应的目的节点，1≤i≤K，其中si，di为当前传输周期的第i个源节点及相应的目的节点，K为当前传输周期中源节点的数目，初始化一个已确定发送时间的节点队列Q0，建立未确定发送时间的节点集合
Figure BDA0002538620910000031
初始化迭代变量r＝1；
S3、从
Figure BDA0002538620910000032
中选择Si，其中
Figure BDA0002538620910000033
表示第r-1次迭代时未确定发送时间的节点集合，对所有Sj＝(sj,dj)∈Qr-1，其中Qr-1表示第r-1次迭代时已确定发送时间的节点队列，Sj＝(sj,dj)表示当前传输周期的第j对源节点和相应的目的节点，1≤j≤K，其中sj，dj为当前传输周期的第j个源节点及相应的目的节点，计算
Figure BDA0002538620910000034
Figure BDA0002538620910000035
其中
Figure BDA0002538620910000041
分别表示si到di、si到dj、sj到di、sj到dj的传播时延，
Figure BDA0002538620910000042
为第j个源节点sj发送包的时刻，
Figure BDA0002538620910000043
为源节点si时间轴上的一个时刻，且满足源节点si在
Figure BDA0002538620910000044
发送包到达目的节点dj的时刻等于源节点sj在Tsj发送包到达目的节点dj的时刻，
Figure BDA0002538620910000045
为源节点si时间轴上的一个时刻，且满足源节点si在
Figure BDA0002538620910000046
发送包到达目的节点di的时刻等于源节点sj在Tsj发送包到达目的节点di的时刻，求第r次迭代时已确定发送时间的节点队列中所有节点数据包到达目的节点的时间映射到源节点si时间轴上的集合
Figure BDA0002538620910000047
其中
Figure BDA0002538620910000048
为第j个源节点sj发送包所需的时长，C为保护时间，求
Figure BDA0002538620910000049
在(-∞,∞)的补集
Figure BDA00025386209100000410
表示第r次迭代时源节点si发送数据包不会与已确定发送时间的节点队列中所有节点数据包发生冲突的时间区间；
S4、将Si从
Figure BDA00025386209100000411
中删除，并加入Qr-1，得到Qr，选择
Figure BDA00025386209100000412
为第i个源节点si发送包的时刻，满足
Figure BDA00025386209100000413
其中Sj＝(sj,dj)∈Qr-1表示当前传输周期的第j对源节点和相应的目的节点，pl∈P，P为网络中所有节点的集合，
Figure BDA00025386209100000414
分别表示源节点si、sj到pl的传播时延；
S5、若r<K，r＝r+1，并重复执行步骤S3～步骤S5，否则令传输的起始时间为T0，第i个源节点si实际发送包的时间采用下式计算
Figure BDA0002538620910000051
传输总时长为
Figure BDA0002538620910000052
其中1≤i≤K，1≤j≤K，pl∈P。
进一步地，所述的步骤S4中，求解式(4)的过程如下：
S4.1、初始化第r次迭代时si的候选发送时间集合
Figure BDA0002538620910000053
Figure BDA0002538620910000054
其中
Figure BDA0002538620910000055
表示
Figure BDA0002538620910000056
中第一个时间区间的终点，
Figure BDA0002538620910000057
表示
Figure BDA0002538620910000058
中的第l个区间，
Figure BDA0002538620910000059
和
Figure BDA00025386209100000510
分别表示
Figure BDA00025386209100000511
中的第l个区间的起点和终点，1≤l≤L，L为
Figure BDA00025386209100000512
包含的区间数目；
S4.2、对
Figure BDA00025386209100000513
中的区间
Figure BDA00025386209100000514
2≤l≤L，若满足
Figure BDA00025386209100000515
Figure BDA00025386209100000516
则将
Figure BDA00025386209100000517
添加到
Figure BDA00025386209100000518
中；
S4.3、对所有候选发送时间
Figure BDA00025386209100000519
计算代价函数
Figure BDA00025386209100000520
其中Sj＝(sj,dj)∈Qr-1，pl∈P，选择令Fk最小的Tk作为Tsi。
进一步地，所述的步骤S3和步骤S4中，在所有的
Figure BDA00025386209100000521
中选择最优的Si和
Figure BDA00025386209100000522
满足
Figure BDA00025386209100000523
其中Si、Sj、Sk分别为第i、第j和第k对源节点和相应的目的节点，
Figure BDA00025386209100000524
Figure BDA00025386209100000525
Figure BDA00025386209100000526
表示源节点sk到pl的传播时延，然后将Si从
Figure BDA00025386209100000527
中删除，并加入Qr-1，得到Qr。
进一步地，若某节点对其他节点进行广播，则Si＝(si,Vi)，其中Vi为si所有目的节点的集合。
进一步地，所述的步骤S3中，从
Figure BDA0002538620910000061
中选择Si，对所有Sj＝(sj,Vj)∈Qr-1，计算
Figure BDA0002538620910000062
Figure BDA0002538620910000063
其中din∈Vi为Vi中的第n个节点，djm∈Vj为Vj中的第m个节点，
Figure BDA0002538620910000064
Figure BDA0002538620910000065
分别表示si到din、si到djm、sj到din、sj到djm的传播时延，Tsj为第j个源节点sj发送包的时刻，
Figure BDA0002538620910000066
为第i个源节点si时间轴上的一个时刻，且满足第i个源节点si在
Figure BDA0002538620910000067
发送包到达目的节点djm的时刻等于源节点sj在
Figure BDA0002538620910000068
发送包到达目的节点djm的时刻，
Figure BDA0002538620910000069
为第i个源节点si时间轴上的一个时刻，且满足第i个源节点si在
Figure BDA00025386209100000610
发送包到达目的节点din的时刻等于源节点sj在
Figure BDA00025386209100000611
发送包到达目的节点din的时刻，并求集合
Figure BDA00025386209100000612
其中
Figure BDA00025386209100000613
为sj发送包所需的时长，C为保护时间，求
Figure BDA00025386209100000614
在(-∞,∞)的补集
Figure BDA00025386209100000615
本发明相对于现有技术具有如下的优点及效果：
1、本发明消除了现有方法对包到达目的节点顺序的约束，可以得到更好的优化效果，令节点的发送时间表更紧凑，在更短时间内完成多个节点的传输，提高了并行通信的效率。
2、本发明可以在优化过程中自动调整节点的发送顺序，无需大量搜索，减少了运算的复杂度。
3、本发明适用范围广，可以广泛用于TDMA和基于握手的竞争式水声网络中。
附图说明
图1是本发明提供的水声网络并行通信的发送时间规划方法流程图。
具体实施方式
为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
实施例
本发明实施例1～3均为一个具有6个节点的水声通信网络，节点按1～6进行编号，各节点均位于水下100米的平面，以节点的水平位置和深度为X、Y、Z轴建立坐标系，以米为单位，节点1～6的坐标分别为(-400，0，100)、(-400，100，100)、(-200，200，100)、(200，200，100)、(400，100，100)、(400，0，100)。每个节点为静态节点且均能监听到其他节点的信号，每个节点配备1个水声调制解调器，上述水声调制解调器的通信方式为全方向、半双工，数据传输速率为1kbps。所有节点具有相同的时钟，每个节点保存一张记录所有节点间传播时延的表，上述传播时延通过计算节点间的距离后除以声速得到，或者通过测量信令中的时间标签与其接收时间之差得到。例如，当声速为1500m/s时，按节点间的距离可计算得到上述节点间的两两传播时延如下表1(单位：秒)：
表1.节点间的两两传播时延表
Figure BDA0002538620910000071
Figure BDA0002538620910000081
本发明实施例1和实施例2中，网络采用竞争式的MAC协议进行接入控制，所有节点采用握手的方式来传输数据，将一个传输周期分为RTS、CTS、DATA和ACK四个阶段。
RTS阶段：当信道空闲且有至少1个节点需要发送数据时，网络进入RTS阶段，需要发起通信的一个或多个源节点在第一个RTS信令发送后的预定时间内，随机选择时间广播RTS信令。经过预定时间后，网络进入CTS阶段。上述RTS信令中包含表示该信令发送时刻的时间标签，所有节点在本传输周期中以第一个RTS信令的时间标签为基准进行计时。
CTS阶段：在CTS阶段中，接收到RTS信令且同意通信的节点在预定时间内的随机时刻广播RTS信令。经过预定时间后，网络进入DATA阶段。
DATA阶段：每个源节点采用本发明提供的发送时间规划方法，计算本节点在本传输周期中发送数据包的时刻，计时至该时刻后，向相应目的节点发送数据。每个源节点采用本发明提供的发送时间规划方法，计算本传输周期中数据包传输所需的总时长，当计时至上述总时长后，进入ACK阶段。
ACK阶段：每个目的节点采用本发明提供的发送时间规划方法，计算本节点在本传输周期中发送ACK或NACK信令的时刻，计时至该时刻后，接收数据正确的目的节点向相应的源节点发送ACK信令，接收数据有错误的目的节点向相应的源节点发送NACK信令。每个源节点采用本发明提供的发送时间规划方法，计算本传输周期中ACK或NACK信令传输所需的总时长，当计时至上述总时长后，本传输周期结束。
实施例1中，采用本发明提供的并行通信发送时间规划方法计算源节点发送数据包的时刻，可以在一个传输周期中互不干扰地并发传送多个数据包，能有效提高水声网络的通信能力，具体采用以下步骤进行，其流程如图1所示：
步骤S1、每个源节点获取当前传输周期所有源节点及其相应的目的节点的列表，以及水声网络中所有源节点要发送包的时长。
步骤S2、初始化已确定发送时间的节点队列和未确定发送时间的节点集合。令Si＝(si,di)表示当前传输周期的第i对源节点和相应的目的节点，1≤i≤K，其中si，di为当前传输周期的第i个源节点及相应的目的节点，K为当前传输周期中源节点的数目，初始化一个已确定发送时间的节点队列Q0，建立未确定发送时间的节点集合
Figure BDA0002538620910000091
初始化迭代变量r＝1。
步骤S3、在未确定发送时间的节点集合中选择一个源节点，并计算它发送数据包不会与已确定发送时间的节点队列中的所有节点数据包发生冲突的时间区间。从
Figure BDA0002538620910000092
中选择Si，其中
Figure BDA0002538620910000093
表示第r-1次迭代时未确定发送时间的节点集合，对所有Sj＝(sj,dj)∈Qr-1，其中Qr-1表示第r-1次迭代时已确定发送时间的节点队列，Sj＝(sj,dj)表示当前传输周期的第j对源节点和相应的目的节点，1≤j≤K，其中sj，dj为当前传输周期的第j个源节点及相应的目的节点，计算
Figure BDA0002538620910000101
Figure BDA0002538620910000102
其中
Figure BDA0002538620910000103
分别表示si到di、si到dj、sj到di、sj到dj的传播时延，
Figure BDA0002538620910000104
为第j个源节点sj发送包的时刻，
Figure BDA0002538620910000105
为源节点si时间轴上的一个时刻，且满足源节点si在
Figure BDA0002538620910000106
发送包到达目的节点dj的时刻等于源节点sj在
Figure BDA0002538620910000107
发送包到达目的节点dj的时刻，
Figure BDA0002538620910000108
为源节点si时间轴上的一个时刻，且满足源节点si在
Figure BDA0002538620910000109
发送包到达目的节点di的时刻等于源节点sj在
Figure BDA00025386209100001010
发送包到达目的节点di的时刻，求第r次迭代时已确定发送时间的节点队列中所有节点数据包到达目的节点的时间映射到源节点si时间轴上的集合
Figure BDA00025386209100001011
其中
Figure BDA00025386209100001012
为第j个源节点sj发送包所需的时长，C为保护时间，求
Figure BDA00025386209100001013
在(-∞,∞)的补集
Figure BDA00025386209100001014
表示第r次迭代时源节点si发送数据包不会与已确定发送时间的节点队列中所有节点数据包发生冲突的时间区间。
步骤S4、选择上述时间区间中令当前传输总时长最短的发送时间，并将该源节点从在未确定发送时间的节点集合中删除，添加到已确定发送时间的节点队列中。将Si从
Figure BDA00025386209100001015
中删除，并加入Qr-1，得到Qr，选择
Figure BDA00025386209100001016
Figure BDA00025386209100001017
为第i个源节点si发送包的时刻，满足
Figure BDA00025386209100001018
其中Sj＝(sj,dj)∈Qr-1表示当前传输周期的第j对源节点和相应的目的节点，pl∈P，P为网络中所有节点的集合，
Figure BDA0002538620910000111
分别表示源节点si、sj到pl的传播时延。
其中，式(4)采用以下方法求解：
步骤S4.1：初始化第r次迭代时si的候选发送时间集合
Figure BDA0002538620910000112
Figure BDA0002538620910000113
其中
Figure BDA0002538620910000114
表示
Figure BDA0002538620910000115
中第一个时间区间的终点，
Figure BDA0002538620910000116
表示
Figure BDA0002538620910000117
中的第l个区间，
Figure BDA0002538620910000118
和
Figure BDA0002538620910000119
分别表示
Figure BDA00025386209100001110
中的第l个区间的起点和终点，1≤l≤L，L为
Figure BDA00025386209100001111
包含的区间数目。
步骤S4.2：对
Figure BDA00025386209100001112
中的区间
Figure BDA00025386209100001113
2≤l≤L，若满足
Figure BDA00025386209100001114
Figure BDA00025386209100001115
则将
Figure BDA00025386209100001116
添加到
Figure BDA00025386209100001117
中。
步骤S4.3：对所有候选发送时间
Figure BDA00025386209100001118
计算代价函数
Figure BDA00025386209100001119
其中Sj＝(sj,dj)∈Qr-1，pl∈P，选择令Fk最小的Tk作为Tsi。
步骤S5、若r<K，r＝r+1，并重复执行步骤S3～步骤S5，否则令传输的起始时间为T0，第i个源节点si实际发送包的时间采用下式计算
Figure BDA00025386209100001120
传输总时长为
Figure BDA00025386209100001121
其中1≤i≤K，1≤j≤K，pl∈P。
以节点1、3、5分别需要向节点2、4、6发送数据包为例，在检测到信道空闲时，节点1、3、5分别广播RTS信令，节点2、4、6接收相应的RTS信令后，分别向节点1、3、5广播回复CTS信令，每个节点侦听并记录下当前传输周期所有源节点和目的节点列表(1，2)、(3，4)、(5，6)。上述实施例中，数据包的长度规定为100Byte，即数据包发送的时长为0.8秒，保护时间设置为0.01秒。
令S1＝(1,2)，S2＝(3,4)，S3＝(5,6)，K＝3，初始化空队列Q0，建立集合
Figure BDA0002538620910000121
初始化迭代变量r＝1。
按S1、S2、S3的顺序从
Figure BDA0002538620910000122
中选择源节点，r＝1时，由于
Figure BDA0002538620910000123
因此
Figure BDA0002538620910000124
选择
Figure BDA0002538620910000125
则区间
Figure BDA0002538620910000126
Figure BDA0002538620910000127
将S1从
Figure BDA0002538620910000128
中删除，并加入Q0，得到Q1＝{S1}。
r＝2时，选择S2，根据式(1)和式(2)，
Figure BDA0002538620910000129
根据式(3)得到并集
Figure BDA00025386209100001210
Figure BDA00025386209100001211
Figure BDA00025386209100001212
中有两个区间，因此L＝2。初始化集合
Figure BDA00025386209100001213
由于区间[0.965,∞)的长度大于
Figure BDA00025386209100001214
因此将0.965添加到
Figure BDA00025386209100001215
中，得到
Figure BDA00025386209100001216
根据式(7)，T1＝-0.892，F1＝2.230，T2＝0.965，F2＝2.187，因此选择
Figure BDA00025386209100001217
将S2从
Figure BDA00025386209100001218
中删除，并加入Q1，得到Q2＝{S1,S2}。
r＝3时，选择S3，根据式(1)和式(2)，
Figure BDA00025386209100001219
Figure BDA00025386209100001220
根据式(3)得到并集
Figure BDA00025386209100001221
Figure BDA00025386209100001222
Figure BDA00025386209100001223
中有三个区间，因此L＝3。初始化集合
Figure BDA00025386209100001224
由于区间[0.343,0.467)的长度小于
Figure BDA00025386209100001225
区间[2.130,∞)的长度大于
Figure BDA00025386209100001226
因此将2.130添加到
Figure BDA00025386209100001227
中，得到
Figure BDA00025386209100001228
根据式(7)，T1＝-1.277，F1＝3.463，T2＝2.130，F2＝3.467，因此选择
Figure BDA0002538620910000131
Figure BDA0002538620910000132
将S3从
Figure BDA0002538620910000133
中删除，并加入Q2，得到Q3＝{S1,S2,S3}。
由于此时r＝K，因此不再迭代，令当前DATA阶段的起始时间为T0＝0，由于
Figure BDA0002538620910000134
最小，则根据式(5)，节点s1、s2、s3的实际发送时间为
Figure BDA0002538620910000135
Figure BDA0002538620910000136
根据式(6)，从第一个源节点发送数据到网络中最后一个节点接收完毕的总传输时长为Ttotal＝3.463秒。当所有节点计时到3.463秒时，DATA阶段结束。
同理可以计算节点2，4，6发送ACK包的时间。
本发明实施例2中，对每一步迭代中Si的选择顺序和发送时间同时进行优化，具体方法是：
步骤S3和步骤S4中，在所有的
Figure BDA0002538620910000137
中选择最优的Si和
Figure BDA0002538620910000138
满足
Figure BDA0002538620910000139
其中Si、Sj、Sk分别为第i、第j和第k对源节点和相应的目的节点，
Figure BDA00025386209100001310
分别表示源节点sk到pl的传播时延，然后将Si从
Figure BDA00025386209100001311
中删除，并加入Qr-1，得到Qr。
以节点1、3、5分别需要向节点2、4、6发送数据为例，根据式(1)～(3)和式(8)，当r＝1时，
Figure BDA00025386209100001312
分别计算当此时选择S1，S2或S3时，最优的发送时间
Figure BDA00025386209100001313
和
Figure BDA00025386209100001314
以及相应的Fk，选择令Fk最小的节点及其发送时间为最优解，可得最优Si为S2＝(3,4)，
Figure BDA00025386209100001315
同理，当r＝2时，最优Si为S3＝(5,6)，
Figure BDA00025386209100001316
当r＝3时，最优Si为S1＝(1,2)，
Figure BDA0002538620910000141
令当前数据传输的起始时间为T0＝0，则根据式(5)，节点s1、s2、s3的实际发送时间为
Figure BDA0002538620910000142
总传输时长为Ttotal＝2.922秒，小于实施例1中未经顺序优化的总传输时长。
本发明实施例3中，所有节点采用时分复用(TDMA)的方式来传输数据，数据包长度为100字节，即每个数据包的发送时长为0.8秒。每个节点发送数据的时隙预先计算好，在网络启动后，每个节点在属于自己的时隙中发送数据。传统的TDMA中，节点的时隙是串行安排的，即某一时刻只有一个节点发送数据，下一节点需等待当前节点的数据传送至所有节点后才能开始，显然会造成极大的浪费。本发明提供的水声网络并行通信的发送时间规划方法，可以规划并发的节点时隙，同时保证数据包到达任意节点时不与其他节点的数据包发生冲突，具体采用以下步骤来规划节点的时隙，即数据包的发送时间：
步骤S1、每个源节点获取当前传输周期所有源节点及其相应的目的节点的列表，以及水声网络中所有源节点要发送包的时长。
上述实施例3中，每个TDMA周期中的源节点均为网络中所有的节点，由于在TDMA中，每个源节点发送数据相当于对所有节点进行广播，因此每个源节点对应的目的节点为网络中所有节点的集合。数据包长度为100Byte，发送一个数据包的时长为0.8秒。
步骤S2、初始化已确定发送时间的节点队列和未确定发送时间的节点集合。令Si＝(si,Vi)，1≤i≤K，其中si当前传输周期的第i个源节点，Vi为si所有目的节点的集合，K为当前传输周期源节点的数目。初始化一个已确定发送时间的节点队列Q0，建立未确定发送时间的节点集合
Figure BDA0002538620910000143
Figure BDA0002538620910000151
初始化迭代变量r＝1。
上述实施例3中，S1＝(1,V)，S2＝(2,V)，S3＝(3,V)，S4＝(4,V)，S5＝(5,V)，S6＝(6,V)，其中V＝(1,2,3,4,5,6)。
步骤S3、在未确定发送时间的节点集合中选择一个源节点，并计算它发送数据包不会与已确定发送时间的节点队列中的所有节点数据包发生冲突的时间区间。从
Figure BDA0002538620910000152
中选择Si，对所有Sj＝(sj,Vj)∈Qr-1，计算
Figure BDA0002538620910000153
Figure BDA0002538620910000154
其中din∈Vi为Vi中的第n个节点，djm∈Vj为Vj中的第m个节点，
Figure BDA0002538620910000155
Figure BDA0002538620910000156
分别表示si到din、si到djm、sj到din、sj到djm的传播时延，
Figure BDA0002538620910000157
为第j个源节点sj发送包的时刻，
Figure BDA0002538620910000158
为第i个源节点si时间轴上的一个时刻，且满足第i个源节点si在
Figure BDA0002538620910000159
发送包到达目的节点djm的时刻等于源节点sj在
Figure BDA00025386209100001510
发送包到达目的节点djm的时刻，
Figure BDA00025386209100001511
为第i个源节点si时间轴上的一个时刻，且满足第i个源节点si在
Figure BDA00025386209100001512
发送包到达目的节点din的时刻等于源节点sj在
Figure BDA00025386209100001513
发送包到达目的节点din的
时刻，并求集合
Figure BDA00025386209100001514
其中
Figure BDA00025386209100001515
为sj发送包所需的时长，C为保护时间，求
Figure BDA00025386209100001516
在(-∞,∞)的补集
Figure BDA00025386209100001517
以已知r＝1时，已确定Q1＝{S3}，
Figure BDA00025386209100001518
Ts3＝0.000，当r＝2时，从
Figure BDA00025386209100001519
中选择S2为例，由于实施例3中，s3和s2的目的节点相同，因此式(9)和(10)相同，只需计算
Figure BDA0002538620910000161
Figure BDA0002538620910000162
根据式(3)得到并集
Figure BDA0002538620910000163
此时
Figure BDA0002538620910000164
步骤S4、选择上述时间区间中令当前传输总时长最短的源节点和发送时间，并将该源节点从在未确定发送时间的节点集合中删除，添加到已确定发送时间的节点队列中。在所有的
Figure BDA0002538620910000165
中选择最优的Si和
Figure BDA0002538620910000166
满足
Figure BDA0002538620910000167
其中Si、Sj、Sk分别为第i、第j和第k对源节点和相应的目的节点，
Figure BDA0002538620910000168
Sj＝(sj,dj)∈Qr-1，
Figure BDA0002538620910000169
分别表示源节点sk到pl的传播时延，然后将Si从
Figure BDA00025386209100001610
中删除，并加入Qr-1，得到Qr。
上述实施例3中，根据式(7)可以得到，当r＝1时，最佳Si为S3＝(3,V)，
Figure BDA00025386209100001611
当r＝2时，最佳Si为S2＝(2,V)，
Figure BDA00025386209100001612
当r＝3时，最佳Si为S0＝(0,V)，
Figure BDA00025386209100001613
当r＝4时，最佳Si为S4＝(4,V)，
Figure BDA00025386209100001614
当r＝5时，最佳Si为S5＝(5,V)，
Figure BDA00025386209100001615
当r＝6时，最佳Si为S6＝(5,V)，
Figure BDA00025386209100001616
步骤S5、若r<K，r＝r+1，并重复执行步骤S3～步骤S5，否则令传输的起始时间为T0，第i个源节点si实际发送包的时间采用下式计算
Figure BDA00025386209100001617
传输总时长为
Figure BDA00025386209100001618
其中1≤i≤K，1≤j≤K，pl∈P。
上述实施例3中，当全部节点发送时间计算出来后，转换为正的发送时间可得
Figure BDA0002538620910000171
Figure BDA0002538620910000172
总传输时长为Ttotal＝6.085秒。
上述实施例为本发明较佳的实施方式，但本发明的实施方式并不受上述实施例的限制，其他的任何未背离本发明的精神实质与原理下所作的改变、修饰、替代、组合、简化，均应为等效的置换方式，都包含在本发明的保护范围之内。

Claims (4)

1.一种水声网络并行通信的发送时间规划方法，该水声网络由多个节点构成，每个节点具有相同的时钟，每个节点保存一张记录所有节点间传播时延的表，其特征在于，在每个传输周期中采用以下步骤进行包的发送时间规划：
S1、每个源节点获取当前传输周期所有源节点及其相应的目的节点的列表，以及水声网络中所有源节点要发送包的时长；
S2、令Si＝(si，di)表示当前传输周期的第i对源节点和相应的目的节点，1≤i≤K，其中si，di为当前传输周期的第i个源节点及相应的目的节点，K为当前传输周期中源节点的数目，初始化一个已确定发送时间的节点队列Q0，建立未确定发送时间的节点集合
Figure FDA0002959427500000011
初始化迭代变量r＝1；
S3、从
Figure FDA0002959427500000012
中选择Si，其中
Figure FDA0002959427500000013
表示第r-1次迭代时未确定发送时间的节点集合，对所有Sj＝(sj，dj)∈Qr-1，其中Qr-1表示第r-1次迭代时已确定发送时间的节点队列，Sj＝(sj，dj)表示当前传输周期的第j对源节点和相应的目的节点，1≤j≤K，其中sj，dj为当前传输周期的第j个源节点及相应的目的节点，计算
Figure FDA0002959427500000014
Figure FDA0002959427500000015
其中
Figure FDA0002959427500000016
分别表示si到di、si到dj、sj到di、sj到dj的传播时延，
Figure FDA0002959427500000017
为第j个源节点sj发送包的时刻，
Figure FDA0002959427500000018
为源节点si时间轴上的一个时刻，且满足源节点si在
Figure FDA0002959427500000019
发送包到达目的节点dj的时刻等于源节点sj在
Figure FDA0002959427500000021
发送包到达目的节点dj的时刻，
Figure FDA0002959427500000022
为源节点si时间轴上的一个时刻，且满足源节点si在
Figure FDA0002959427500000023
发送包到达目的节点di的时刻等于源节点sj在
Figure FDA0002959427500000024
发送包到达目的节点di的时刻，求第r次迭代时已确定发送时间的节点队列中所有节点数据包到达目的节点的时间映射到源节点si时间轴上的集合
Figure FDA0002959427500000025
其中
Figure FDA0002959427500000026
为第j个源节点sj发送包所需的时长，C为保护时间，求
Figure FDA0002959427500000027
在(-∞，∞)的补集
Figure FDA0002959427500000028
表示第r次迭代时源节点si发送数据包不会与已确定发送时间的节点队列中所有节点数据包发生冲突的时间区间；
S4、将Si从
Figure FDA0002959427500000029
中删除，并加入Qr-1，得到Qr，选择
Figure FDA00029594275000000210
Figure FDA00029594275000000211
为第i个源节点si发送包的时刻，满足
Figure FDA00029594275000000212
Figure FDA00029594275000000213
其中Sj＝(sj，dj)∈Qr-1表示当前传输周期的第j对源节点和相应的目的节点，
Figure DEST_PATH_IMAGE002
∈P，P为网络中所有节点的集合，
Figure FDA00029594275000000214
分别表示源节点si、sj到
Figure 562649DEST_PATH_IMAGE002
的传播时延；
S5、若r＜K，r＝r+1，并重复执行步骤S3～步骤S5，否则令传输的起始时间为T0，第i个源节点si实际发送包的时间采用下式计算
Figure FDA00029594275000000215
传输总时长为
Figure FDA00029594275000000216
其中1≤i≤K，1≤j≤K，pl∈P；；其中，所述的步骤S4中，求解式(4)的过程如下：
S4.1、初始化第r次迭代时si的候选发送时间集合
Figure FDA0002959427500000031
Figure FDA0002959427500000032
其中
Figure FDA0002959427500000033
表示
Figure FDA0002959427500000034
中第一个时间区间的终点，
Figure FDA0002959427500000035
表示
Figure FDA0002959427500000036
中的第l个区间，
Figure FDA0002959427500000037
和
Figure FDA0002959427500000038
分别表示
Figure FDA0002959427500000039
中的第l个区间的起点和终点，
Figure DEST_PATH_IMAGE004
，L为
Figure FDA00029594275000000310
包含的区间数目；
S4.2、对
Figure FDA00029594275000000311
中的区间
Figure FDA00029594275000000312
若满足
Figure FDA00029594275000000313
Figure FDA00029594275000000314
则将
Figure FDA00029594275000000315
添加到
Figure FDA00029594275000000316
中；
S4.3、对所有候选发送时间
Figure FDA00029594275000000317
计算代价函数
Figure FDA00029594275000000318
其中Sj＝(sj，dj)∈Qr-1，
Figure 994636DEST_PATH_IMAGE002
∈P，选择令Fk最小的Tk作为
Figure FDA00029594275000000319
2.根据权利要求1所述的一种水声网络并行通信的发送时间规划方法，其特征在于，所述的步骤S3和步骤S4中，在所有的
Figure FDA00029594275000000320
中选择最优的Si和
Figure FDA00029594275000000321
满足
Figure FDA00029594275000000322
Figure FDA00029594275000000323
其中Si、Sj、Sk分别为第i、第j和第k对源节点和相应的目的节点，
Figure FDA00029594275000000324
Figure FDA00029594275000000325
Sj＝(sj，dj)∈Qr-1，
Figure 774373DEST_PATH_IMAGE002
∈P，
Figure FDA00029594275000000326
表示源节点sk到
Figure 169583DEST_PATH_IMAGE002
的传播时延，然后将Si从
Figure FDA00029594275000000327
中删除，并加入Qr-1，得到Qr。
3.根据权利要求1所述的一种水声网络并行通信的发送时间规划方法，其特征在于，若某节点对其他节点进行广播，则Si＝(si，Vi)，其中Vi为si所有目的节点的集合。
4.根据权利要求3所述的一种水声网络并行通信的发送时间规划方法，其特征在于，所述的步骤S3中，从
Figure FDA0002959427500000041
中选择Si，对所有Sj＝(sj，Vj)∈Qr-1，计算
Figure FDA0002959427500000042
Figure FDA0002959427500000043
其中din∈Vi为Vi中的第n个节点，djm∈Vj为Vj中的第m个节点，
Figure FDA0002959427500000044
Figure FDA0002959427500000045
分别表示si到din、si到djm、sj到din、sj到djm的传播时延，
Figure FDA0002959427500000046
为第j个源节点sj发送包的时刻，
Figure FDA0002959427500000047
为第i个源节点si时间轴上的一个时刻，且满足第i个源节点si在
Figure FDA0002959427500000048
发送包到达目的节点djm的时刻等于源节点sj在
Figure FDA0002959427500000049
发送包到达目的节点djm的时刻，
Figure FDA00029594275000000410
为第i个源节点si时间轴上的一个时刻，且满足第i个源节点si在
Figure FDA00029594275000000411
发送包到达目的节点din的时刻等于源节点sj在
Figure FDA00029594275000000412
发送包到达目的节点din的时刻，并求集合
Figure FDA00029594275000000413
其中
Figure FDA00029594275000000414
为sj发送包所需的时长，C为保护时间，求
Figure FDA00029594275000000415
在(-∞，∞)的补集
Figure FDA00029594275000000416
CN202010540228.5A 2020-06-15 2020-06-15 一种水声网络并行通信的发送时间规划方法 Expired - Fee Related CN111800200B (zh)

Priority Applications (1)

Application Number Priority Date Filing Date Title
CN202010540228.5A CN111800200B (zh) 2020-06-15 2020-06-15 一种水声网络并行通信的发送时间规划方法

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
CN202010540228.5A CN111800200B (zh) 2020-06-15 2020-06-15 一种水声网络并行通信的发送时间规划方法

Publications (2)

Publication Number Publication Date
CN111800200A CN111800200A (zh) 2020-10-20
CN111800200B true CN111800200B (zh) 2021-05-14

Family

ID=72804336

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202010540228.5A Expired - Fee Related CN111800200B (zh) 2020-06-15 2020-06-15 一种水声网络并行通信的发送时间规划方法

Country Status (1)

Country Link
CN (1) CN111800200B (zh)

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
CN114172591B (zh) * 2021-11-15 2023-09-05 中国船舶重工集团公司第七一五研究所 多体制水声通信网络高效并发传输方法
CN114244780B (zh) * 2021-12-27 2024-04-16 海光信息技术股份有限公司 一种数据传输方法、数据传输装置和相关设备
CN114499804B (zh) * 2021-12-31 2023-01-03 广东省国土资源测绘院 一种多信道水声网络的并行通信方法、设备及介质

Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20110022746A (ko) * 2009-08-24 2011-03-08 한국해양연구원 클러스터 수중 음향 네트워크를 위한 이동 노드 기반의 시간 분할 다중 접속 매체 접속 제어 방법
CN104754740A (zh) * 2013-12-31 2015-07-01 电信科学技术研究院 资源分配方法和装置
CN105744640A (zh) * 2016-01-14 2016-07-06 南京航空航天大学 一种基于邻居波束对准与跟踪的移动ad hoc网络定向时分接入协议

Family Cites Families (9)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7375602B2 (en) * 2000-03-07 2008-05-20 Board Of Regents, The University Of Texas System Methods for propagating a non sinusoidal signal without distortion in dispersive lossy media
CN1794880B (zh) * 2005-12-21 2010-05-05 中国科学院计算技术研究所 一种光突发交换网中的并行调度处理方法
KR20090015487A (ko) * 2007-08-08 2009-02-12 강릉대학교산학협력단 클러스터 기반의 센서 네트워크의 오류를 탐지하고복구하는 방법
CN102056324B (zh) * 2010-12-22 2013-02-06 中国人民解放军理工大学 基于令牌控制冲突解析的协同载波侦听多址接入方法
CN102098113B (zh) * 2011-02-25 2013-05-08 东南大学 基于aloha和tdma的水声传感器网络mac层协议的实现方法
CN102122993B (zh) * 2011-03-11 2013-09-25 华南理工大学 一种远距离水声通信的方法和装置
CN102201873B (zh) * 2011-05-20 2013-11-20 东南大学 一种水声通信网络的分布式动态时分多址协议方法
CN102811115B (zh) * 2012-07-23 2015-07-01 山东科技大学 一种延长弹性波透地通信距离的方法
EP3043521B1 (en) * 2013-10-15 2018-06-06 Huawei Technologies Co., Ltd. Method and device for sending crossover command

Patent Citations (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR20110022746A (ko) * 2009-08-24 2011-03-08 한국해양연구원 클러스터 수중 음향 네트워크를 위한 이동 노드 기반의 시간 분할 다중 접속 매체 접속 제어 방법
CN104754740A (zh) * 2013-12-31 2015-07-01 电信科学技术研究院 资源分配方法和装置
CN105744640A (zh) * 2016-01-14 2016-07-06 南京航空航天大学 一种基于邻居波束对准与跟踪的移动ad hoc网络定向时分接入协议

Also Published As

Publication number Publication date
CN111800200A (zh) 2020-10-20

Similar Documents

Publication Publication Date Title
CN111800200B (zh) 一种水声网络并行通信的发送时间规划方法
US8406139B2 (en) Method and apparatus for efficient transfer of data over a network
CN107071829B (zh) 一种面向数据收集任务的水声网络媒体接入控制方法
CN106332299B (zh) 包含运动节点的竞争信道水声网络多节点并行通信方法
CN102098093A (zh) 一种用于水声通信网的tdma方法
CN104486005A (zh) 一种适用于竞争信道水声网络的多节点快速通信方法
CN105357158A (zh) 水下认知网络中节点准确高效接入多信道的方法
CN111050393B (zh) 一种uwb定位系统
CN105101086B (zh) 一种基于车辆密度分布的数据传输路径选择方法
CN111193997A (zh) 一种uwb定位系统的到达时间差测量与校准方法
CN106899981B (zh) 一种节点发送时间和功率联合优化的水声网络通信方法
CN114125069B (zh) 一种水声网络多对一并行传输mac协议的实现方法
CN114531716A (zh) 一种基于能耗和链路质量的路由选择方法
CN111641990B (zh) 高数据包投递率与能量有效性的水声传感器网络传输方法
CN103796230A (zh) 水下传感器网络中基于功率控制的介质访问控制方法
CN110769519B (zh) 一种分布式多信道水声网络通信方法
CN104735722A (zh) 一种高效节能的传感器网络数据传输方法
CN111246534A (zh) 一种不需要时钟同步的水下移动节点网络自组织方法
CN108541021B (zh) 一种适用于水下滑翔机组网的动态信道分配方法
CN102065513B (zh) 提高AdHoc网络邻节点列表精确性的方法
CN104486348B (zh) 考虑节点业务流量的水下声信道网络媒体接入控制方法
CN112839352A (zh) 带有并行传输机制的竞争性mac协议的设计
CN112437478A (zh) 一种基于可变时隙的高效mac协议
KR101996971B1 (ko) 이동성 추적 기반의 시분할 다중접속 방법
Saravanan et al. MAC Layer Communication Protocol design using Stochastic Network Calculus for Underwater Agriculture Farming

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant
CF01 Termination of patent right due to non-payment of annual fee

Granted publication date: 20210514

CF01 Termination of patent right due to non-payment of annual fee