基于图结构任务调度的并行测距方法

• 摘要：

  本发明公开了一种基于图结构任务调度的并行测距方法,主要解决目前声学测距时耗时久成本高的问题.主要方案为:1)在N个移动设备中选取一个作为主节点,将其余移动设备与该主节点相连接构成测距网络;2)主节点发布测距任务,生成测距的总任务集Γ;3)生成单步测距任务集Γ_q并进行测距;4)在单步测距任务集Γ_q和总任务集Γ中删除测距成功和测距失败且达到重试次数上限的任务,判断Γ_q和Γ的状态:若Γ_q不为空,则测距失败任务重试次数加1,返回步骤3);若Γ_q为空,则再判断总任务集Γ状态:若Γ不为空,则返回步骤3),否则,则测距结束.本发明并行测距用时短,设备携带方便,适用范围广,可用于大范围的多节点定位.

• 专利类型：

  发明专利

• 申请/专利号：

  CN201710274312.5

• 申请日期：

  2017.04.25

• 公开/公告号：

  CN107144843A

• 公开/公告日：

  2017-09-08

• 发明人：

  齐飞 黄原成 夏朝辉 石光明 林杰 王晓甜

• 申请人：

  西安电子科技大学

• 主分类号：

  G01S15/08(2006.01)I,G,G01,G01S,G01S15

• 分类号：

  G01S15/08(2006.01)I,G01S7/52(2006.01)I,H04W64/00(2009.01)I,H04W84/12(2009.01)I,G,H,G01,H04,G01S,H04W,G01S15,G01S7,H04W64,H04W84,G01S15/08,G01S7/52,H04W64/00,H04W84/12

• 主权项：

  一种基于图结构任务调度的并行测距方法,包括:(1)根据移动设备数量设网络中有N个节点,并在在众多设备中选定一个移动设备作为主节点M,其它节点作为从节点,并分别与主节点连接构成整个测距网络;(2)主节点M发布测距任务,生成测距的总任务集Γ＝{T_ij},再由并行测距调度算法生成单步测距任务集Γ_q,其中T_ij表示第i个节点与第j个节点之间的待测距离,1≤i≤N,1≤j≤N,i≠j;(2a)将当前总任务集Γ映射为一个图G,图中顶点即测距任务的节点,边则对应于测距任务;设置测距任务重试次数上限r,将所有测距任务的重试次数初始化为1;(2b)初始化单步测距任务集Γ_q和发射节点集I_q,使其全为空集,设置节点测量次数m,将所有节点的被测次数m初始化为0;(2c)从图G中选择至少有一条临边且m为0的节点作为发射节点i,将节点i加入到发射点集I_q,任取与发射节点i连接的一点作为应答节点j,将节点i与节点j被测次数m置1,生成测距任务T_ij,并将其加入到单步测距任务集Γ_q;以此方法继续寻找下一个发射点以及其对应的应答节点,将所有节点进行配对生成测距任务加入到单步测距任务集,对剩下的独立节点则保留至下次测距任务;(3)依据单步测距任务集Γ_q及其中的发射节点集I_q和各发射节点对应的应答节点进行测距:(3a)指示所有发射节点集中的节点i∈I_q通过发射器发射相应的声音信号S_i,同时节点自身对该信号通过接收器进行接收,记录发射节点i自身接收到信号S_i的时间T_1i;(3b)指示所有发射节点对应的应答节点j通过接收器接收发射节点i的标示信号S_i,并记录接收到信号S_i的时间T_2i;(3c)应答节点j收到信号S_i后发射应答信号S_j,同时对该信号进行接收,并记录应答节点j自身接收到信号S_j的时间T_1j;(3d)发射节点i接收应答节点j的应答信号S_j,并记录接收到相应信号的时间T_2j;(4)根据(3)中所记录的时间信号,计算出发射节点与应答节点之间的距离;(5)判断单步任务集Γ_q与总任务集Γ的状态,直至任务全部测完;(5a)将测距成功和测距失败但到达重试次数上限的任务T_ij从单步测距任务集和总任务集Γ中删除;(5b)判断单步测距任务集Γ_q是否为空:如果不为空,说明存在测距失败且重试次数未达到上限的测距任务T_ij,将该任务重试次数加1,并将该测距任务T_ij重新加入到总任务集Γ,再返回步骤(2b)生成下一次单步测距任务集Γ_q重新测试;如果为空,则进一步判断总任务集Γ是否为空,若总任务集Γ不为空,则返回步骤(2b),若总任务集Γ为空,则测距完成.