prophet路由详解 机会网络 DTN网络 ONE模拟器

news/2025/3/19 16:10:13/

ONE模拟器

  • 简介
  • 代码
  • 代码详解

简介

prophet算法是机会网络中的经典算法，在Probabilistic routing in intermittently connected networks，2003中提出
论文链接

代码

/* * Copyright 2010 Aalto University, ComNet* Released under GPLv3. See LICENSE.txt for details. */
package routing;import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import core.Settings;import core.*;
import routing.util.RoutingInfo;import util.Tuple;/*** Implementation of PRoPHET router as described in * <I>Probabilistic routing in intermittently connected networks</I> by* Anders Lindgren et al.*/public class ProphetRouter extends ActiveRouter {/** delivery predictability initialization constant*/public static final double P_INIT = 0.75;/** delivery predictability transitivity scaling constant default value */public static final double DEFAULT_BETA = 0.25;/** delivery predictability aging constant */public static final double GAMMA = 0.98;/** Prophet router's setting namespace ({@value})*/public static final String PROPHET_NS = "ProphetRouter";/*** Number of seconds in time unit -setting id ({@value}).* How many seconds one time unit is when calculating aging of * delivery predictions. Should be tweaked for the scenario.*/public static final String SECONDS_IN_UNIT_S ="secondsInTimeUnit";/*** Transitivity scaling constant (beta) -setting id ({@value}).* Default value for setting is {@link #DEFAULT_BETA}.*/public static final String BETA_S = "beta";/** the value of nrof seconds in time unit -setting */private int secondsInTimeUnit;/** value of beta setting */private double beta;/** delivery predictabilities */private Map<DTNHost, Double> preds;/** last delivery predictability update (sim)time */private double lastAgeUpdate;/*** Constructor. Creates a new message router based on the settings in* the given Settings object.* @param s The settings object*/public ProphetRouter(Settings s) {super(s);Settings prophetSettings = new Settings(PROPHET_NS);secondsInTimeUnit = prophetSettings.getInt(SECONDS_IN_UNIT_S);if (prophetSettings.contains(BETA_S)) {beta = prophetSettings.getDouble(BETA_S);}else {beta = DEFAULT_BETA;}initPreds();}/*** Copyconstructor.* @param r The router prototype where setting values are copied from*/protected ProphetRouter(ProphetRouter r) {super(r);this.secondsInTimeUnit = r.secondsInTimeUnit;this.beta = r.beta;initPreds();}/*** Initializes predictability hash*/private void initPreds() {this.preds = new HashMap<DTNHost, Double>();}@Overridepublic void changedConnection(Connection con) {super.changedConnection(con);if (con.isUp()) {DTNHost otherHost = con.getOtherNode(getHost());updateDeliveryPredFor(otherHost);updateTransitivePreds(otherHost);}}/*** Updates delivery predictions for a host.* <CODE>P(a,b) = P(a,b)_old + (1 - P(a,b)_old) * P_INIT</CODE>* @param host The host we just met*/public void updateDeliveryPredFor(DTNHost host) {double oldValue = getPredFor(host);double newValue = oldValue + (1 - oldValue) * P_INIT;preds.put(host, newValue);}/*** Returns the current prediction (P) value for a host or 0 if entry for* the host doesn't exist.* @param host The host to look the P for* @return the current P value*/public double getPredFor(DTNHost host) {ageDeliveryPreds(); // make sure preds are updated before gettingif (preds.containsKey(host)) {return preds.get(host);}else {return 0;}}/*** Updates transitive (A->B->C) delivery predictions.* <CODE>P(a,c) = P(a,c)_old + (1 - P(a,c)_old) * P(a,b) * P(b,c) * BETA* </CODE>* @param host The B host who we just met*/private void updateTransitivePreds(DTNHost host) {MessageRouter otherRouter = host.getRouter();assert otherRouter instanceof ProphetRouter : "PRoPHET only works " +" with other routers of same type";double pForHost = getPredFor(host); // P(a,b)Map<DTNHost, Double> othersPreds =((ProphetRouter)otherRouter).getDeliveryPreds();for (Map.Entry<DTNHost, Double> e : othersPreds.entrySet()) {if (e.getKey() == getHost()) {continue; // don't add yourself}double pOld = getPredFor(e.getKey()); // P(a,c)_olddouble pNew = pOld + ( 1 - pOld) * pForHost * e.getValue() * beta;preds.put(e.getKey(), pNew);}}/*** Ages all entries in the delivery predictions.* <CODE>P(a,b) = P(a,b)_old * (GAMMA ^ k)</CODE>, where k is number of* time units that have elapsed since the last time the metric was aged.* @see #SECONDS_IN_UNIT_S*/private void ageDeliveryPreds() {double timeDiff = (SimClock.getTime() - this.lastAgeUpdate) / secondsInTimeUnit;if (timeDiff == 0) {return;}double mult = Math.pow(GAMMA, timeDiff);for (Map.Entry<DTNHost, Double> e : preds.entrySet()) {e.setValue(e.getValue()*mult);}this.lastAgeUpdate = SimClock.getTime();}/*** Returns a map of this router's delivery predictions* @return a map of this router's delivery predictions*/public Map<DTNHost, Double> getDeliveryPreds() {ageDeliveryPreds(); // make sure the aging is donereturn this.preds;}@Overridepublic void update() {super.update();if (!canStartTransfer() ||isTransferring()) {return; // nothing to transfer or is currently transferring }// try messages that could be delivered to final recipientif (exchangeDeliverableMessages() != null) {return;}tryOtherMessages();		}/*** Tries to send all other messages to all connected hosts ordered by* their delivery probability* @return The return value of {@link #tryMessagesForConnected(List)}*/private Tuple<Message, Connection> tryOtherMessages() {List<Tuple<Message, Connection>> messages = new ArrayList<Tuple<Message, Connection>>(); Collection<Message> msgCollection = getMessageCollection();/* for all connected hosts collect all messages that have a higherprobability of delivery by the other host */for (Connection con : getConnections()) {DTNHost other = con.getOtherNode(getHost());ProphetRouter othRouter = (ProphetRouter)other.getRouter();if (othRouter.isTransferring()) {continue; // skip hosts that are transferring}for (Message m : msgCollection) {if (othRouter.hasMessage(m.getId())) {continue; // skip messages that the other one has}if (othRouter.getPredFor(m.getTo()) > getPredFor(m.getTo())) {// the other node has higher probability of deliverymessages.add(new Tuple<Message, Connection>(m,con));}}			}if (messages.size() == 0) {return null;}// sort the message-connection tuplesCollections.sort(messages, new TupleComparator());return tryMessagesForConnected(messages);	// try to send messages}/*** Comparator for Message-Connection-Tuples that orders the tuples by* their delivery probability by the host on the other side of the * connection (GRTRMax)*/private class TupleComparator implements Comparator <Tuple<Message, Connection>> {public int compare(Tuple<Message, Connection> tuple1,Tuple<Message, Connection> tuple2) {// delivery probability of tuple1's message with tuple1's connectiondouble p1 = ((ProphetRouter)tuple1.getValue().getOtherNode(getHost()).getRouter()).getPredFor(tuple1.getKey().getTo());// -"- tuple2...double p2 = ((ProphetRouter)tuple2.getValue().getOtherNode(getHost()).getRouter()).getPredFor(tuple2.getKey().getTo());// bigger probability should come firstif (p2-p1 == 0) {/* equal probabilities -> let queue mode decide */return 0;
//				return compareByQueueMode(tuple1.getKey(), tuple2.getKey());}else if (p2-p1 < 0) {return -1;}else {return 1;}}}@Overridepublic RoutingInfo getRoutingInfo() {ageDeliveryPreds();RoutingInfo top = super.getRoutingInfo();RoutingInfo ri = new RoutingInfo(preds.size() + " delivery prediction(s)");for (Map.Entry<DTNHost, Double> e : preds.entrySet()) {DTNHost host = e.getKey();Double value = e.getValue();ri.addMoreInfo(new RoutingInfo(String.format("%s : %.6f", host, value)));}top.addMoreInfo(ri);return top;}@Overridepublic MessageRouter replicate() {ProphetRouter r = new ProphetRouter(this);return r;}}

代码详解

静态变量

	/** 影响直接相遇概率的更新，P_INIT */public static final double P_INIT = 0.75;/** beta的default值 */public static final double DEFAULT_BETA = 0.25;/** 衰老率，值越小衰老速度越快 */public static final double GAMMA = 0.98;/** router name* /public static final String PROPHET_NS = "ProphetRouter";/** 时间片长度配置名 */public static final String SECONDS_IN_UNIT_S ="secondsInTimeUnit";/** beta配置名 */public static final String BETA_S = "beta";/** 时间片长度 */private int secondsInTimeUnit;/** 概率传递率，在间接更新传递率时，越高，间接更新比例越大 */private double beta;/** 存储概率值的 Map */private Map<DTNHost, Double> preds;/** 上次概率更新时间 */private double lastAgeUpdate;

ProphetRouter
构造器。根据给定设置对象中的设置创建新的消息路由器
初始化变量：secondsInTimeUnit，在默认的配置文件中，ProphetRouter.secondsInTimeUnit = 30
可以通过配置文件初始化beta，类型为double
初始化存储Prophet概率值的HashMap
最后是每个路由都要有的路由复制器

public ProphetRouter(Settings s) {super(s);Settings prophetSettings = new Settings(PROPHET_NS);secondsInTimeUnit = prophetSettings.getInt(SECONDS_IN_UNIT_S);if (prophetSettings.contains(BETA_S)) {beta = prophetSettings.getDouble(BETA_S);}else {beta = DEFAULT_BETA;}initPreds();
}
private void initPreds() {this.preds = new HashMap<DTNHost, Double>();
}
protected ProphetRouter(ProphetRouter r) {super(r);this.secondsInTimeUnit = r.secondsInTimeUnit;this.beta = r.beta;initPreds();
}

changedConnection
继承自父类，每次节点连接开始和结束都要调用
每次连接开始时，执行：
updateDeliveryPredFor 更新与本次相遇节点间的Prophet概率值
updateTransitivePreds 更新与其他节点间的Prophet概率值

public void changedConnection(Connection con) {super.changedConnection(con);if (con.isUp()) {DTNHost otherHost = con.getOtherNode(getHost());updateDeliveryPredFor(otherHost);updateTransitivePreds(otherHost);}
}

private void updateDeliveryPredFor(DTNHost host)
更新与本次相遇节点间的Prophet概率值
newValue = oldValue + (1 - oldValue) * P_INIT

private void updateDeliveryPredFor(DTNHost host) {double oldValue = getPredFor(host);double newValue = oldValue + (1 - oldValue) * P_INIT;preds.put(host, newValue);
}

P_INIT的值不可以设置
设置时需要添加以下代码：

/*ProphetRouter类中*/
public static final String P_INIT_S = "prophetInit";/*public ProphetRouter(Settings s)中*/
if (prophetSettings.contains(P_INIT_S )) {beta = prophetSettings.getDouble(P_INIT_S );
}/*配置文件中，[0,1]，类型double*/
ProphetRouter.prophetInit= 0.5

getPredFor
获取某个具体的Prophet概率值
先执行ageDeliveryPreds所有的Prophet概率值进行时间衰老，再返回Prophet概率值

public double getPredFor(DTNHost host) {ageDeliveryPreds(); if (preds.containsKey(host)) {return preds.get(host);}else {return 0;}
}

updateTransitivePreds
更新与其他节点间的Prophet概率值
例：a与b相遇更新a与c的Prophet概率值
pacNew = pacOld + ( 1 - pacOld) * pab* pbc * beta

private void updateTransitivePreds(DTNHost host) {MessageRouter otherRouter = host.getRouter();assert otherRouter instanceof ProphetRouter : "PRoPHET only works " + " with other routers of same type";double pForHost = getPredFor(host); // P(a,b)Map<DTNHost, Double> othersPreds = ((ProphetRouter)otherRouter).getDeliveryPreds();for (Map.Entry<DTNHost, Double> e : othersPreds.entrySet()) {if (e.getKey() == getHost()) {continue; // don't add yourself}double pOld = getPredFor(e.getKey()); // P(a,c)_olddouble pNew = pOld + ( 1 - pOld) * pForHost * e.getValue() * beta;preds.put(e.getKey(), pNew);}
}

ageDeliveryPreds
根据时间衰老Prophet概率值
p = p*GAMMA^k
k为上次更新概率后所过去的时间，单位秒

private void ageDeliveryPreds() {double timeDiff = (SimClock.getTime() - this.lastAgeUpdate) / secondsInTimeUnit;if (timeDiff == 0) {return;}double mult = Math.pow(GAMMA, timeDiff);for (Map.Entry<DTNHost, Double> e : preds.entrySet()) {e.setValue(e.getValue()*mult);}this.lastAgeUpdate = SimClock.getTime();
}

getDeliveryPreds
获取存储Prophet概率值的HashMap

private Map<DTNHost, Double> getDeliveryPreds() {ageDeliveryPreds(); // make sure the aging is donereturn this.preds;
}

update
继承，每模拟一分钟检查一次。检查所有发送连接，有完成或中断的，中止；删除TTL<=0的消息；更新能量
router的刷新器
首先传输目的地时相遇节点的消息
再传输其他消息tryOtherMessages

public void update() {super.update();if (!canStartTransfer() ||isTransferring()) {return; // nothing to transfer or is currently transferring }// try messages that could be delivered to final recipientif (exchangeDeliverableMessages() != null) {return;}tryOtherMessages();		
}

tryOtherMessages
如果相遇节点的传输概率大于自己的就传输，传输时按照Prophet概率值从大到小排序

private Tuple<Message, Connection> tryOtherMessages() {List<Tuple<Message, Connection>> messages = new ArrayList<Tuple<Message, Connection>>(); Collection<Message> msgCollection = getMessageCollection();/* for all connected hosts collect all messages that have a higherprobability of delivery by the other host */for (Connection con : getConnections()) {DTNHost other = con.getOtherNode(getHost());ProphetRouter othRouter = (ProphetRouter)other.getRouter();if (othRouter.isTransferring()) {continue; // skip hosts that are transferring}for (Message m : msgCollection) {if (othRouter.hasMessage(m.getId())) {continue; // skip messages that the other one has}if (othRouter.getPredFor(m.getTo()) > getPredFor(m.getTo())) {// the other node has higher probability of deliverymessages.add(new Tuple<Message, Connection>(m,con));}}			}if (messages.size() == 0) {return null;}// sort the message-connection tuplesCollections.sort(messages, new TupleComparator());return tryMessagesForConnected(messages);	// try to send messages
}

TupleComparator
上一个方法中的排序的比较器

private class TupleComparator implements Comparator <Tuple<Message, Connection>> {public int compare(Tuple<Message, Connection> tuple1,Tuple<Message, Connection> tuple2) {// delivery probability of tuple1's message with tuple1's connectiondouble p1 = ((ProphetRouter)tuple1.getValue().getOtherNode(getHost()).getRouter()).getPredFor(tuple1.getKey().getTo());// -"- tuple2...double p2 = ((ProphetRouter)tuple2.getValue().getOtherNode(getHost()).getRouter()).getPredFor(tuple2.getKey().getTo());// bigger probability should come firstif (p2-p1 == 0) {/* equal probabilities -> let queue mode decide */return compareByQueueMode(tuple1.getKey(), tuple2.getKey());}else if (p2-p1 < 0) {return -1;}else {return 1;}}
}

getRoutingInfo，replicate
每个router必须的解释函数和实例化函数


http://www.ppmy.cn/news/781952.html

相关文章

什么是DTD

什么是DTD

DTD(Document Type Definition) 是一套关于标记符的语法规则。DTD 是一种保证XML文档格式正确的有效方法&#xff0c;可通过比较XML文档和DTD文件来看文档是否符合规范&#xff0c;元素和标签使用是否正确。 用于定义XML的结构和语法规则&#xff0c;避免出现数据的混乱 还用…
阅读更多...
DTN学习，theONE模拟器网络相关资料整理

DTN学习，theONE模拟器网络相关资料整理

下面是一个百度空间的&#xff1a; http://hi.baidu.com/jensenliao 博客园的一篇博客&#xff1a;theONE模拟器简介&#xff08;主要讲述&#xff0c;软件配置&#xff0c;软件结构&#xff09; http://www.cnblogs.com/dreamfactory/archive/2012/07/27/2612215.html 博客…
阅读更多...
tsn

tsn

TSN 1.如何提帧 1.1数据集准备 下载网址&#xff1a;http://crcv.ucf.edu/data/UCF101/UCF101.rar 下载成功后的UCF文件夹如下所示&#xff1a; 该文件夹下是各种动作的视频文件&#xff0c;共有101种类别 下图是UCF101在进行训练和测试时&#xff0c;分割的依据文件 1.2…
阅读更多...
【C语言初阶（10）】函数练习题

【C语言初阶（10）】函数练习题

文章目录 1. 判断素数2. 判断闰年3. 函数实现二分查找4. 记录函数调用次数 1. 判断素数 题目内容 写一个函数可以判断一个数是不是素数。 素数 素数也叫做质数&#xff0c;一个只能被 1 和它本身整除的数字称之为素数。 例如&#xff1a;7 这个数字只能被 1 和 它本身&#x…
阅读更多...
DTD详解

DTD详解

基本概述 文档类型定义(Document Type Definition)是一套为了进行程序间的数据交换而建立的关于标记符的语法规则。它是标准通用标记语言(SGML)和可扩展标记语言(XML)1.0版规格的一部分&#xff0c;文档可根据某种DTD语法规则验证格式是否符合此规则。文档类型定义也可用做保证…
阅读更多...
DHT网络简介

DHT网络简介

DHT网络全称为分布式哈希表网络(Distributed Hash Table net)&#xff0c;是一种由键值对唯一标识的信息按某种协议被分散在多个节点上的“非中心化服务”网络。可在分布式对等网络环境中进行存储、检索、查询、等管理数据。其数据大规模分散在多个节点上的网络。可以有效避免单…
阅读更多...
DTN中基于两跳ACK 确认机制的备用副本转发算法

DTN中基于两跳ACK 确认机制的备用副本转发算法

DTN中基于两跳ACK 确认机制的备用副本转发算法 摘要 针对DTN在遇到路由空洞问题&#xff08;由于某些原因&#xff0c;没有合适的下一跳节点&#xff09;时缺乏有效回避路由空洞的方法导致信息端到端传输时延较大的问题&#xff0c;提出了DTN中基于两跳ACK &#xff08;ACK1 …
阅读更多...
DTn one 的学习，，，

DTn one 的学习，，，

在今天开始学习了one的代码学习 《机会网络模拟器ONE及其扩展研究*》王朕王新华隋敬麒这。 想看看在one中有没有应用层的使用 看了想明天看 《基于社会网络特性的机会计算服务平台》 陈加忠1, 鞠增伟1, 陈常念1, 李 榕1, 夏 涛1, 王 冼 收获是对DTn中的主要包的主要功能有个…
阅读更多...
最新文章

Copyright @ 2022~2023