会员体验
专利管家(专利管理)
工作空间(专利管理)
风险监控(情报监控)
数据分析(专利分析)
侵权分析(诉讼无效)
联系我们
交流群
官方交流:
QQ群: 891211   
微信请扫码    >>>
现在联系顾问~
首页 / 专利库 / 深空网 / 一种基于DTN深空传感器网络多径路由方法

一种基于DTN深空传感器网络多径路由方法

申请号 CN201210560455.X 申请日 2012-12-20 公开(公告)号 CN103036783A 公开(公告)日 2013-04-10
申请人 山东黄金集团有限公司; 发明人 傅学生; 周贤伟; 李菲;
摘要 本发明公开了一种基于DTN深空传感器网络多径路由方法,其特征在于,包括如下步骤:(1)路由发现,包括请求query过程和回复reply过程,找出数据分组发送的主路径和备用路径;(2)路由维护;(3)计算节点a与每个相邻节点之间的效用值;(4)数据分组在备份路径上传递,节点a发送RERR分组到源节点,开始路由重新发现过程,更新网络情况和拓扑,使路由保持最新和最佳。本发明给出了基于最大效用值的多径路由方法,在链路连接概率一个影响因子决定的基础上,增加了一个剩余能量因子,如果没有考虑能量问题,即使节点间连接概率为1,剩余能量很低时,也无法完成数据分组的正确转发。
权利要求

1.一种基于DTN深空传感器网络多径路由方法,其特征在于,包括如下步骤:

(1)路由发现,包括请求query过程和回复reply过程,找出数据分组发送的主路径和备用路径;

(2)路由维护,当主路径正常时,数据分组在主路径上正常传输,当主路径断开时,主路径断开处的传感器节点a执行一跳数据广播到它的邻居节点,节点a在数据分组头部指出链路断开,邻居节点接收到该数据分组时,邻居节点在其备用路由表中查找手否有到目的节点的下一跳节点的表项,若存在,邻居节点缓存该数据分组,并向节点a回复收到数据分组的确认分组REQ,向节点a确认是否可以传输该数据分组,判断节点a收到的确认分组REQ的数量,如果节点a收到一个确认分组REQ,节点a向此相邻节点发送回复分组REP,允许数据分组经过此相邻节点传递,如果节点a收到多个确认分组REQ,转步骤(3);

(3)计算节点a与每个相邻节点之间的效用值,选择效用值最大的相邻节点,节点a向效用值最大的相邻节点发送回复分组REP,允许数据分组经过此相邻节点传递,同时节点a向其它相邻节点发送回复分组ERR,收到回复分组ERR的相邻节点将缓存中的数据删除,同时根据上述计算结果更新自身的备用路由表;

(4)数据分组在备份路径上传递,节点a发送RERR分组到源节点,开始路由重新发现过程,更新网络情况和拓扑,使路由保持最新和最佳。

2.根据权利要求1所述基于DTN深空传感器网络多径路由方法,其特征在于,所述步骤(1)包括如下步骤:(1.1)请求query过程:当一个源节点需要发起一个到目的节点的数据会话,它先查找自己的路由表,如果自己的路由表中存在到目的节点的理由信息,直接发送RREQ分组到目的节点,当发现路由表中没有任何到目的节点的路由信息时,转步骤(1.2);

(1.2)源节点通过洪泛RREQ请求分组的方式搜索路由,每个RREQ分组拥有一个唯一的标识符,这样节点可以发现和丢弃复制分组,以避免回路的出现,当中间节点接收到一个非复制RREQ分组时,它在其路由表中记录先前的跳和源节点信息,然后,中间节点广播分组,或者如果它的路由表中存在到目的节点的路由就发送RREP分组给源节点;

(1.3)当目的节点接收到RREQ分组时,它按照已经选择的路由向源节点发送RREP分组;

(1.4)回复reply过程:当不是主路径上的节点杂乱地监听到由其相邻节点传输的非针对自身的RREP分组时,它在其备用路由表中记录下这个相邻节点,使其成为该节点到目的节点的下一跳节点,如果监听节点在主路径的多个中间节点的射频范围内,该监听节点可能接收到来自相同路由的许多RREP分组,在这种情况下,监听节点选择最佳的路由插入到它的备用路由表中,当RREP分组到达路由的源节点时,源节点和目的节点之间的主路径被建立,同时,在备用路由表中拥有到目的节点表项的节点成为网状网的一部分,主路径和备份路径一起构成了网状结构,呈现鱼骨状。

3.根据权利要求1所述基于DTN深空传感器网络多径路由方法,其特征在于,所述步骤(3)的计算规则如下:(3.1)相邻节点能量更新,根据传感器节点自身特性,已知传感器节点的剩余能量值,利用本次剩余能量与前一次的剩余能量,对下一次能量的剩余情况进行预测,估计相邻节点目前的剩余能量是否还满足一次数据传输所需能量:其中,δ为修正因子,当δ为1时,节点剩余能量线性变化,否则为非线性变化,根据当时情况进行设置,如果tbefore→tnow,即Δt→0,Ebefore→Enow,△E越接近下一时刻的能量变化,得到的节点剩余能量将越准确,E为估计一次数据传递所需要的能量,Ebefore代表前一次的剩余能量,Enow代表本次剩余能量,tbefore代表前一次发送数据分组的时刻,tnow代表本次发送数据分组的时刻,t代表数据分组发送的时刻;

当一个节点位于多个节点的传输范围内时,考虑节点会传递所有接收到的数据,需要对所有消耗的能量进行加权求和;

其中,δ(i)为第i个节点与该节点相遇时的修正因子,E为估计m次数据传递所需要的能量,Ebefore(i)代表前一次的第i个节点的剩余能量,Enow(i)代表本次第i个节点剩余能量,tbefore(i)代表前一次第i个节点发送数据分组的时刻,tnow(i)代表本次第i个节点发送数据分组的时刻,t(i)代表第i个节点的数据分组发送的时刻,如果该节点同时与多个节点进行数据传输,那么该节点的能量将快速降低,如果只与一个结果传输数据,那么节点的能量可能呈线性下降趋势,这两种情况都将在节点剩余能量为0时不在可用,节点进入休眠状态;

(3.2)能量衰减,如果没有与任何节点相遇,则该节点处于休眠状态,节点能量消耗极少,甚至处于太阳照射范围内时,利用太阳能补充能量,此时剩余能量如下式:σ

E=Ebefore*ε

其中ε是衰减因子,σ是该节点最后一次传输数据到当前的时间长度,这种情况当节点剩余能量等于初始大小时,不再充电;

(3.3)定义效用函数,使用效用理论建立效用函数,综合考虑链路连接概率和能量因素:

U(a,b)=W1P(a,b)+W2Eb

其中,假设节点a将向节点b传输数据,P(a,b)为节点a和b之间的链路连接概率,Eb为节点b的剩余能量值,W1和W2为权值,满足W1+W2=1,U(a,b)表示节点a和b之间的效用值,通过比较该值的大小对下一跳备份路径进行选择。

说明书全文

一种基于DTN深空传感器网络多径路由方法

技术领域

[0001] 本发明涉及在深空传感器网络中节点之间备份多路径中下一条节点的选择问题,具体地讲,涉及一种基于DTN深空传感器网络多径路由方法。

背景技术

[0002] 对未知的求索驱使人类一步步“迈向”太空,人类探索宇宙演化过程、揭示生命起源、寻找生命存在的脚步一刻也没有停止。无线传感器网络被认为是21世纪重要的技术之一,其在环境探测中担任着重要的角色,在人类探索深空的过程中也越来越发挥重要的作用。
[0003] 然而,处于深空的传感器网络由于环境因素影响,与传统的传感器网络存在很大不同,这使得深空传感器网络成为一种受限网络。如何有效改善这种情况呢?2003年,Kevin Fall提出了一种全新的网络体系结构——DTN。它是一种运行在区域网络之上的网络,能够实现区域网络互联,并且它的网络体系结构包含了许多能够解决受限网络问题的特性。
[0004] 对于网络而言,路由研究是一个重要的研究内容。深空传感器网络运行在恶劣甚至是未知的远程环境中,由于太阳电磁辐射干扰、节点移动、节点自身缺乏资源等,建立的路由可能很容易断开,因此设计有效的策略延长网络的生存寿命是深空传感器网络的核心问题。这使得为其设计路由协议成为一个富有挑战的问题。实际上,为了缓解这些问题,可以采用多径路由的方式。多径路由为主路径寻找替代路径,以替代方式增加路由过程的效率。它利用资源冗余和多样性支持错误容忍,负载平衡,端到端传递时延最小化和降低能量消耗等需求。同时,有文献已经证明选择多条路径时,维护比最短路径长很多的替代路径和多于两条或三条的替代路径都是无益处的。此外,多径路由应该是按需的(on-demand)和备份多路径方式,这样可以有效减少开销和对存储资源的利用。
[0005] 由此,本文对深空传感器网络提出一种基于DTN的多径路由,使能有效缓解数据分组在传输中遇到的上述问题。同时,结合对链路连接概率的研究,加入对节点剩余能量的考虑,建立效用函数。在选择多条路径时,有文献已经证明维护比最短路径长很多的替代路径和多于两条或三条的替代路径都是无益处的。因此,在选择备用路径时,利用得到的效用函数选择最佳路径,能够有效减少开销和利用资源。

发明内容

[0006] 本发明要解决的技术问题是提供一种基于DTN深空传感器网络多径路由方法,更好的均衡网络负载,充分利用网络资源。
[0007] 本发明采用如下技术手段实现发明目的:
[0008] 一种基于DTN深空传感器网络多径路由方法,其特征在于,包括如下步骤:
[0009] (1)路由发现,包括请求query过程和回复reply过程,找出数据分组发送的主路径和备用路径;
[0010] (2)路由维护,当主路径正常时,数据分组在主路径上正常传输,当主路径断开时,主路径断开处的传感器节点a执行一跳数据广播到它的邻居节点,节点a在数据分组头部指出链路断开,邻居节点接收到该数据分组时,邻居节点在其备用路由表中查找手否有到目的节点的下一跳节点的表项,若存在,邻居节点缓存该数据分组,并向节点a回复收到数据分组的确认分组REQ,向节点a确认是否可以传输该数据分组,判断节点a收到的确认分组REQ的数量,如果节点a收到一个确认分组REQ,节点a向此相邻节点发送回复分组REP,允许数据分组经过此相邻节点传递,如果节点a收到多个确认分组REQ,转步骤(3);
[0011] (3)计算节点a与每个相邻节点之间的效用值,选择效用值最大的相邻节点,节点a向效用值最大的相邻节点发送回复分组REP,允许数据分组经过此相邻节点传递,同时节点a向其它相邻节点发送回复分组ERR,收到回复分组ERR的相邻节点将缓存中的数据删除,同时根据上述计算结果更新自身的备用路由表;
[0012] (4)数据分组在备份路径上传递,节点a发送RERR分组到源节点,开始路由重新发现过程,更新网络情况和拓扑,使路由保持最新和最佳。
[0013] 作为对本技术方案的进一步限定,所述步骤(1)包括如下步骤:
[0014] (1.1)请求query过程:当一个源节点需要发起一个到目的节点的数据会话,它先查找自己的路由表,如果自己的路由表中存在到目的节点的理由信息,直接发送RREQ分组到目的节点,当发现路由表中没有任何到目的节点的路由信息时,转步骤(1.2);
[0015] (1.2)源节点通过洪泛RREQ请求分组的方式搜索路由,每个RREQ分组拥有一个唯一的标识符,这样节点可以发现和丢弃复制分组,以避免回路的出现,当中间节点接收到一个非复制RREQ分组时,它在其路由表中记录先前的跳和源节点信息,然后,中间节点广播分组,或者如果它的路由表中存在到目的节点的路由就发送RREP分组给源节点;
[0016] (1.3)当目的节点接收到RREQ分组时,它按照已经选择的路由向源节点发送RREP分组;
[0017] (1.4)回复re ply过程:当不是主路径上的节点杂乱地监听到由其相邻节点传输的非针对自身的RREP分组时,它在其备用路由表中记录下这个相邻节点,使其成为该节点到目的节点的下一跳节点,如果监听节点在主路径的多个中间节点的射频范围内,该监听节点可能接收到来自相同路由的许多RREP分组,在这种情况下,监听节点选择最佳的路由插入到它的备用路由表中,当RREP分组到达路由的源节点时,源节点和目的节点之间的主路径被建立,同时,在备用路由表中拥有到目的节点表项的节点成为网状网的一部分,主路径和备份路径一起构成了网状结构,呈现鱼骨状。
[0018] 作为对本技术方案的进一步限定,所述步骤(3)的计算规则如下:
[0019] (3.1)相邻节点能量更新,根据传感器节点自身特性,已知传感器节点的剩余能量值,利用本次剩余能量与前一次的剩余能量,对下一次能量的剩余情况进行预测,估计相邻节点目前的剩余能量是否还满足一次数据传输所需能量:
[0020]
[0021] 其中,δ为修正因子,当δ为1时,节点剩余能量线性变化,否则为非线性变化,根据当时情况进行设置,如果tbefore→tnow,即Δt→0,
[0022] Ebefore→Enow,△E越接近下一时刻的能量变化,得到的节点剩余能量将越准确,E为估计一次数据传递所需要的能量,Ebefore代表前一次的剩余能量,Enow代表本次剩余能量,tbefore代表前一次发送数据分组的时刻,tnow代表本次发送数据分组的时刻,t代表数据分组发送的时刻;
[0023] 当一个节点位于多个节点的传输范围内时,考虑节点会传递所有接收到的数据,需要对所有消耗的能量进行加权求和;
[0024]
[0025] 其中,δ(i)为第i个节点与该节点相遇时的修正因子,E为估计m次数据传递所需要的能量,Ebefore(i)代表前一次的第i个节点的剩余能量,Enow(i)代表本次第i个节点剩余能量,tbefore(i)代表前一次第i个节点发送数据分组的时刻,tnow(i)代表本次第i个节点发送数据分组的时刻,t(i)代表第i个节点的数据分组发送的时刻,如果该节点同时与多个节点进行数据传输,那么该节点的能量将快速降低,如果只与一个结果传输数据,那么节点的能量可能呈线性下降趋势,这两种情况都将在节点剩余能量为0时不在可用,节点进入休眠状态;
[0026] (3.2)能量衰减,如果没有与任何节点相遇,则该节点处于休眠状态,节点能量消耗极少,甚至处于太阳照射范围内时,利用太阳能补充能量,此时剩余能量如下式:
[0027] E=Ebefore*εσ
[0028] 其中ε是衰减因子,σ是该节点最后一次传输数据到当前的时间长度,这种情况当节点剩余能量等于初始大小时,不再充电;
[0029] (3.3)定义效用函数,使用效用理论建立效用函数,综合考虑链路连接概率和能量因素:
[0030] U(a,b)=W1P(a,b)+W2Eb
[0031] 其中,假设节点a将向节点b传输数据,P(a,b)为节点a和b之间的链路连接概率,Eb为节点b的剩余能量值,W1和W2为权值,满足W1+W2=1,U(a,b)表示节点a和b之间的效用值,通过比较该值的大小对下一跳备份路径进行选择。
[0032] 与现有技术相比,本发明的优点和积极效果是:本发明给出了基于最大效用值的多径路由方法,在链路连接概率一个影响因子决定的基础上,增加了一个剩余能量因子,如果没有考虑能量问题,即使节点间连接概率为1,剩余能量很低时,也无法完成数据分组的正确转发。通过在两个因子中间寻求效率最大化,数据分组能够在一条最佳的路径上传输,能够均衡网络负载,适应网络的动态变化,充分利用网络资源。本发明在改善数据投递率、端到端平均时延和吞吐量方面,能够有效地改善已有方法的性能,具有一定的竞争力。在实际应用中,可根据本发明给出的分析结果和实际需要选择最佳的备份路径,确保数据传输效率。同时,也可为利用概率方法解决路由选择以及对其相关方法的改进提供一种有效参考。

附图说明

[0033] 图1是本发明的路由流程图。
[0034] 图2-图6是替代路径建立过程的流程图。

具体实施方式

[0035] 下面结合附图和优选实施例对本发明作更进一步的详细描述。
[0036] 参见图1,由于深空传感器网络中资源有限,采用按需路由方式,只有当源节点有分组要发送时,它才广播RREQ分组,同时,选择备份多路径方法,路由机制中路由维护为重点内容,当链路断开时,节点发现多个节点都可以用来传输数据,但其中每个节点传输的效率不同,利用本发明选择出最佳节点提供数据传输的可靠性。具体的路由机制建立过程如下:
[0037] (1)路由发现,包括请求query过程和回复reply过程,找出数据分组发送的主路径和备用路径;
[0038] (2)路由维护,当主路径正常时,数据分组在主路径上正常传输,当主路径断开时,主路径断开处的传感器节点a执行一跳数据广播到它的邻居节点,节点a在数据分组头部指出链路断开,邻居节点接收到该数据分组时,邻居节点在其备用路由表中查找手否有到目的节点的下一跳节点的表项,若存在,邻居节点缓存该数据分组,并向节点a回复收到数据分组的确认分组REQ,向节点a确认是否可以传输该数据分组,判断节点a收到的确认分组REQ的数量,如果节点a收到一个确认分组REQ,节点a向此相邻节点发送回复分组REP,允许数据分组经过此相邻节点传递,如果节点a收到多个确认分组REQ,转步骤(3);
[0039] (3)计算节点a与每个相邻节点之间的效用值,选择效用值最大的相邻节点,节点a向效用值最大的相邻节点发送回复分组REP,允许数据分组经过此相邻节点传递,同时节点a向其它相邻节点发送回复分组ERR,收到回复分组ERR的相邻节点将缓存中的数据删除,同时根据上述计算结果更新自身的备用路由表;
[0040] (4)数据分组在备份路径上传递,节点a发送RERR分组到源节点,开始路由重新发现过程,更新网络情况和拓扑,使路由保持最新和最佳。
[0041] 所述步骤(1)包括如下步骤:
[0042] (1.1)请求query过程:当一个源节点需要发起一个到目的节点的数据会话,它先查找自己的路由表,如果自己的路由表中存在到目的节点的理由信息,直接发送RREQ分组到目的节点,当发现路由表中没有任何到目的节点的路由信息时,转步骤(1.2);
[0043] (1.2)源节点通过洪泛RREQ请求分组的方式搜索路由,每个RREQ分组拥有一个唯一的标识符,这样节点可以发现和丢弃复制分组,以避免回路的出现,当中间节点接收到一个非复制RREQ分组时,它在其路由表中记录先前的跳和源节点信息,然后,中间节点广播分组,或者如果它的路由表中存在到目的节点的路由就发送RREP分组给源节点;
[0044] (1.3)当目的节点接收到RREQ分组时,它按照已经选择的路由向源节点发送RREP分组;
[0045] (1.4)回复reply过程:当不是主路径上的节点杂乱地监听到由其相邻节点传输的非针对自身的RREP分组时,它在其备用路由表中记录下这个相邻节点,使其成为该节点到目的节点的下一跳节点,如果监听节点在主路径的多个中间节点的射频范围内,该监听节点可能接收到来自相同路由的许多RREP分组,在这种情况下,监听节点选择最佳的路由插入到它的备用路由表中,当RREP分组到达路由的源节点时,源节点和目的节点之间的主路径被建立,同时,在备用路由表中拥有到目的节点表项的节点成为网状网的一部分,主路径和备份路径一起构成了网状结构,呈现鱼骨状。
[0046] 所述步骤(3)的计算规则如下:
[0047] (3.1)相邻节点能量更新,根据传感器节点自身特性,已知传感器节点的剩余能量值,利用本次剩余能量与前一次的剩余能量,对下一次能量的剩余情况进行预测,估计相邻节点目前的剩余能量是否还满足一次数据传输所需能量:
[0048]
[0049] 其中,δ为修正因子,当δ为1时,节点剩余能量线性变化,否则为非线性变化,根据当时情况进行设置,如果tbefore→tnow,即Δt→0,
[0050] Ebefore→Enow,△E越接近下一时刻的能量变化,得到的节点剩余能量将越准确,E为估计一次数据传递所需要的能量,Ebefore代表前一次的剩余能量,Enow代表本次剩余能量,tbefore代表前一次发送数据分组的时刻,tnow代表本次发送数据分组的时刻,t代表数据分组发送的时刻;
[0051] 当一个节点位于多个节点的传输范围内时,考虑节点会传递所有接收到的数据,需要对所有消耗的能量进行加权求和;
[0052]
[0053] 其中,δ(i)为第i个节点与该节点相遇时的修正因子,E为估计m次数据传递所需要的能量,Ebefore(i)代表前一次的第i个节点的剩余能量,Enow(i)代表本次第i个节点剩余能量,tbefore(i)代表前一次第i个节点发送数据分组的时刻,tnow(i)代表本次第i个节点发送数据分组的时刻,t(i)代表第i个节点的数据分组发送的时刻,如果该节点同时与多个节点进行数据传输,那么该节点的能量将快速降低,如果只与一个结果传输数据,那么节点的能量可能呈线性下降趋势,这两种情况都将在节点剩余能量为0时不在可用,节点进入休眠状态;
[0054] (3.2)能量衰减,如果没有与任何节点相遇,则该节点处于休眠状态,节点能量消耗极少,甚至处于太阳照射范围内时,利用太阳能补充能量,此时剩余能量如下式:
[0055] E=Ebefore*εσ
[0056] 其中ε是衰减因子,σ是该节点最后一次传输数据到当前的时间长度,这种情况当节点剩余能量等于初始大小时,不再充电;
[0057] (3.3)定义效用函数,使用效用理论建立效用函数,综合考虑链路连接概率和能量因素:
[0058] U(a,b)=W1P(a,b)+W2Eb
[0059] 其中,假设节点a将向节点b传输数据,P(a,b)为节点a和b之间的链路连接概率,Eb为节点b的剩余能量值,W1和W2为权值,满足W1+W2=1,U(a,b)表示节点a和b之间的效用值,通过比较该值的大小对下一跳备份路径进行选择。
[0060] 参见图2-图6,下面结合一个实例对本发明作进一步的说明,经过路由发现后,主路径已被建立。
[0061] 过程(a):目的节点D发送RREP到节点C,利用无线通信性质由此开始建立替代路径。对于节点y和z,它们在节点D的传播范围内,因此能够监听节点D收发数据分组的情况,并将其作为一个表项插入到它们的备用路由表中,过程如图2所示。
[0062] 过程(b):节点C、y、z同时接收到RREP分组,但只有主路径上的节点C转发它到节点B。同样,一跳邻居节点w、x、y、z、D监听到RREP分组传输情况。对节点w和x,它们记录节点C作为到目的节点D的下一跳节点在它们的备用路由表中。然而,对节点y和z,它们不更新其备用路由表,因为在其备用路由表中已经存在到目的节点D的下一跳节点。对节点D,它不用回复节点C的RREP传输,因为它就是目的节点,过程如图3所示。
[0063] 过程(c):当RREP分组到达源节点S时,主路径和备份路径建立完成,形成网状结构,过程如图4所示。
[0064] 过程(d):当数据开始传输后,由于各种原因主路径断开,此时开始使用备份路径。例如,由于节点B的移动,节点C不再在其一跳邻居节点的射频范围内。当接收到来自节点A的数据分组后,节点B想要转发它到节点C。此时因为节点C不可到达分组将传递失败。
然后,节点B向它的邻居广播数据分组,节点A、w和x监听并接收到该分组,节点A将丢弃它因为发现是副本,节点w和x通过查阅备份路由表它们可以作为传输分组的下一跳节点,然后同时向节点B发送REQ,请求传输数据。在节点B中,经计算得出,节点w的效用值大于节点x的效用值,因此节点B向节点w发送REP表示可以传输该数据组分,向节点x发送ERR,节点x删除缓存中的数据,同时向源节点发送RERR分组说明主路径已经断开。此时备份路径为,过程如图5所示。
[0065] 示例中,目的节点D经过备份路径接收到数据,这比主路径跳数多。但是,使用备份路径也可以有和主路径相同的跳数。如果节点B和节点C之间的链路失败,节点z转发来自节点B的数据直接到目的节点D。因此,数据传输路径和主路径拥有相同的跳数,如图6所示。
[0066] 当然,上述说明并非对本发明的限制,本发明也不仅限于上述举例,本技术领域的普通技术人员在本发明的实质范围内所做出的变化、改型、添加或替换,也属于本发明的保护范围。