机会网络中一种高效路由算法.pdf

(19)中华人民共和国国家知识产权局(12)发明专利申请(10)申请公布号CN105791120A(43)申请公布日2016.07.20(21)申请号201610288465.0(22)申请日2016.05.03(71)申请人哈尔滨工业大学深圳研究生院地址518000广东省深圳市南山区西丽镇深圳大学城哈工大校区(72)发明人王岢叶允明徐晓飞李旭涛聂哲(74)专利代理机构深圳市科吉华烽知识产权事务所(普通合伙)44248代理人马世中曹大鹏(51)Int.Cl.H04L12/721(2013.01)H04L12/727(2013.01)权利要求书2页说明书12页附图2页(54)发明名称机会网络中一种高效路由算法(57)摘要本发明提出了一种机会网络中的高效路由算法（PMSF算法），在SAW的基础上进行改进，在散发阶段充分考虑中继节点的传递性能，使用了改进的Prophet投递预测函数作为效用值对消息副本进行分配，投递预测函数表示的传输预测值越大，中继节点传递消息的成功率越高，故应分配给该节点更多的消息副本，摒弃了经典SAW消息散发阶段盲目的均等散发机制。同时，将等待阶段的DirectDelivery被动路由方式改为主动路由，并将等待阶段命名为转发阶段，以更好的贴合主动路由阶段的消息多跳转发机制，利用马尔可夫时间间隔预测模型，尽量将消息转发给较快便能与目的节点相遇的中继节点。本发明同时兼顾了高效和可信的原则，使得副本快速扩散、有效传输，又能保证传输的稳定性和可靠性。CN105791120ACN105791120A权利要求书1/2页1.一种机会网络中的高效路由算法，其特征在于：所述算法为利用Prophet投递预测函数和马尔可夫模型改进SprayandWait的混合路由算法PMSF，所述算法包括：在散发spray阶段，根据Prophet投递预测函数得到的投递概率对相遇节点的质量和传递潜能进行评估，在计算Prophet投递概率时充分考虑链路传输的可靠性，根据所述投递概率散发分配不同数量的副本；在转发阶段，将被动路由的等待阶段修改为主动路由的多跳转发阶段，在该过程中引入马尔可夫模型预测相遇节点到目的节点的时间，并选取能在最短时间间隔内到达目的节点的节点作为中继节点；循环执行上述散发和转发阶段，直至消息到达目的节点。2.根据权利要求1所述的高效路由算法，其特征在于：根据节点间相遇的历史信息，求解出节点相遇持续时间的平均值，用该值去衡量链路消息传输的可靠性。3.根据权利要求1所述的高效路由算法，其特征在于：所述spray阶段的详细流程为：假设消息msg的目的节点是D，当持有msg副本个数为L的节点A与节点B建立临时通信链路时，A和B分别更新各自到目的节点的传输预测值，同时，双方交换彼此具有ACK确认信息的CMI消息列表，丢弃那些已被目的节点确认接收到的消息副本；接下来，判断节点A，B是否满足spray阶段消息转发的条件，当且仅当A中msg的副本的数量大于1且B中没有msg的副本才散发该消息，若任一条件得不到满足就不能散发该消息；同时，还需要判断B到目的节点D的传输预测值是否大于A到D的传输预测值，只有在大于A的情况下才进行消息转发；当B准备接收A散发的消息msg的副本时，B需要检查自身的缓存空间是不是足以容纳新的消息，如果不充足，需要按照FIFO的思想删除最早进入到缓存队列的消息，随后将消息副本放入腾出空间的节点缓存中，同时计算和修改B应该持有msg副本的数量，如果B是msg的目的节点，把msg放入CMI对应的ACK消息确认列表中；否则，msg会继续存储在A的缓存之中，等待良好的投递时机；然后，源节点和中继节点都将循环执行该步骤，直到自身所剩消息副本的数量减少为1时，转入消息投递过程的转发阶段。4.根据权利要求3所述的高效路由算法，其特征在于：计算A要分配给B的消息副本数具体为：假设某个时刻，携带源消息的节点A与节点B相遇，该消息的副本数量为L且目的地为节点D，具体数值由下式计算所得：其中，mD表示以节点D作为目的节点的消息，表示节点A当前持有的消息副本数量，是重新分配给节点A的消息副本数量，P(A,D)，P(B,D)表示两节点间成功投递消息的传输预测值。5.根据权利要求1所述的高效路由算法，其特征在于：所述转发阶段的详细流程为：当携带消息msg(副本数为1)的节点A与节点B相遇时，首先利用节点间相遇的历史信息并结合马尔可夫模型预测自身到目的节点D的相遇时间间隔；此处用KP(A,D)和KP(B,D)分别表示A和B在未来一段时间内与D再次相遇的时间间隔，当KP(B,D)＜KP(A,D)且B中不包含msg的任何副本时，A便把msg直接转发给B相反，A将继续携带msg；若A在某一时刻同时与多个节点相遇，求解出能在最短时间内到达D的节点，包括A自身，把ms