一种基于间断连通自组织网络延时有限的概率路由方法

摘要

本发明提出了一种应用于间断连通自组织网络的概率路由方法，本发明的基本思想是利用间断连通自组织网络中节点移动的统计分布规律，按照用户消息指定的必需传输概率RDP以及传输延时进行预判是否产生消息副本，以及计算产生的消息副本的必要传输概率RDP的值，并对源消息中RDP值进行更新的过程。本发明保证了消息能够在所指定的送达时间内的，满足用户期望的必要传输概率RDP值，并且可以根据消息的RDP值和送达时间要求来控制消息的传输开销，摒弃了不必要的消息转发，从而有效的降低了间断连通自组织网络中的消息传输开销。

主权项

1、一种基于间断连通自组织网络延时有限的概率路由方法，其特征在于：包括消息副本预判机制、消息副本概率计算机制、源节点概率更新机制，且三种机制顺序执行；1)消息副本预判机制，当网络节点A遇到了非目的节点B时，节点A通过消息副本预判机制来决定是否为节点B创建消息副本，该机制主要用来预判节点A是否需要产生消息副本，其步骤如下：步骤1：节点A向节点B发送确认消息，用来确认节点B中是否已经存在待转发的消息m，当节点B接收到此确认消息后，给节点A回复信息，当B已经存在消息m，此预判副本产生机制结束，当B中不存在消息m，预判副本产生机制进入步骤2；步骤2：节点A通过查找保存在自身节点上的平均相遇时间表，得到节点A与目的节点D之间的相遇时间τ_ad，根据指数分布概率公式能计算出节点A与目的节点D之间的直接传输概率p_dt为：$\mathrm{Pr}\{{\tau }_{\mathrm{ad}}\le d_{\mathrm{bounded}}\}=1-e^{-{\lambda }_{\mathrm{ad}}{\tau }_{\mathrm{ad}}},$d_bounded≥0，其中λ_ad＝1/τ_ad，τ_ad为时间表中记录的节点A与D间的平均相遇时间；步骤3：比较消息m的RDP指标p_m与p_dt的大小，当p_m＜p_dt，不需要产生消息副本，消息副本预判结束；当p_m＞p_dt，则产生消息副本m’，通过消息副本概率计算机制得到m’的RDP指标p_m’；2)消息副本概率计算机制，计算消息副本m’中RDP字段值p_m’，步骤如下：步骤一：节点A利用Dijkstra最短路算法从平均相遇时间表中找出相遇节点B到目的节点D的最短路，并由公式计算得出节点B沿最短路将消息在延时d_bounded内送达到目的节点D的概率p_est，其中：$C_{i,n-1}=\underset{j\ne i}{\Pi }\frac{{\lambda }_{k_j{k}_{j+1}}}{{\lambda }_{k_j{k}_{j+1}}-{\lambda }_{k_i{k}_{i+1}}},$${\lambda }_{k_i{k}_{i+1}}=1/{\bar{\tau }}_{k_i{k}_{i+1}},$为节点B到D最短路上的相邻两点k_ik_i+1间的平均相遇时间，Δ_BD为节点B沿最短路径到节点D的端到端的传输延时；步骤二：由于源节点A到目的节点D的各条消息传输路径相互独立，则由消息副本预判机制所得到的直接传输概率p_dt和源消息m的RDP值p_m，通过公式P_n＝(P_m-P_dt)/(1-P_dt)计算出消息副本m’的期望传输概率p_n；步骤三：节点A比较p_est和p_n大小，将较小的数值赋给p_m’，即：当p_est≥p_n，则p_m’＝p_n，将消息副本m’发送给节点B；当p_est＜p_n，则p_m’＝p_est，将消息副本m’发送给节点B；3)源节点概率更新机制，是更新源节点A中消息m的RDP字段值p_m，更新过程为：由源消息m的必需送达概率p_m和消息副本m’的必需送达概率p_m’，根据公式P_m＝(P_m-P_m’)/(1-P_m’)计算得更新的消息m的必需送达概率p_m。