The ONE使用笔记:Prophet路由

Prophet利用节点间之前的相遇情况为每个节点对求得投递预测值delivery predictabilities,若转发节点的delivery predictabilities高于发送节点,那么就将消息复制转发。本文介绍Prophet路由相关技术细节。

1. 路由策略

介绍Prophet路由的文章如下:

LINDGREN, Anders, DORIA, Avri, et SCHELEN, Olov. Probabilistic routing in intermittently connected networks. In : Service Assurance with Partial and Intermittent Resources. Springer Berlin Heidelberg, 2004. p. 239-254. BibTex

对于DTN路由,毋庸置疑的是:将一个消息复制转发给更多的节点,那么成功投递的可能性就越大,最极端的就是Epidemic,但缺点也很明显,占用太多系统资源(如缓冲区);同理,将一个消息尽可能少复制转发给其他节点,投递率就会下降,最极端的就是DirectDelivery。

问题就来了,如何更有效地复制转发消息,即将消息复制转发给那些更有可能将消息成功投递的节点。Prophet就是用节点间之前相遇的历史信息,动态更新链接的投递可能值(delivery predictabilities)。求delivery predictabilities包含3部分,公式如下:

image

(1)encounter

节点间相遇越频繁说明delivery predictability越高,Pinit是一个初始化常数,在[0,1]间取值。

(2)age

如果两个节点间有一段时间没相遇了,那么delivery predictability需要降低。Gamma是指aging constant,在[0,1)间取值,k指距离上次更新的time units数。

(3)transitive

考虑节点间的传递性,如节点A经常遇到节点BB经常遇见C,那么连接(a,c)delivery predictability也应该更高。β是放大常数,在[0,1]间取值。

2. Prophet

2.1 常数及设置文件

由上述分析可知,Prophet涉及到三个常数和一个变量:Pinit, Gamma, β, k。三个常数如下:

//ProphetRouter.java
public static final double P_INIT = 0.75;       //delivery predictability initialization constant
public static final double DEFAULT_BETA = 0.25; //delivery predictability transitivity scaling constant default value
public static final double GAMMA = 0.98;        //delivery predictability aging constant

private double beta;    //可以通过设置文件设置,如ProphetRouter.beta = 0.25

3个常数,只有β能通过设置文件改变,设置文件如下:

//设置文件
Group.router = ProphetRouter
ProphetRouter.beta = 0.25               //默认值为0.25
ProphetRouter.secondsInTimeUnit = 30    //多少秒更新一次(age)

2.2 更新delivery predictabilities

首先需要存储每个节点对的delivery predictabilities,用HashMap存储。每个节点的私有变量preds存储本节点与其他节点的delivery predictabilities,如(a, b), (a, c), (a, …)。源代码如下:

//ProphetRouter.java
private Map<DTNHost, Double> preds; //delivery predictabilities

private void initPreds() {
    this.preds = new HashMap<DTNHost, Double>();
}

2.2.1 何时更新

对于encountertransitive,当链接建立时更新;对于age,每隔secondsInTimeUnit更新一次。值得注意的是,更新age比较被动。updateDeliveryPredForupdateTransitivePreds都会调用getPredFor,取得节点的delivery predictabilitiesgetPredFor函数会调用ageDeliveryPreds更新因age带来的影响。源代码如下:

//ProphetRouter.java    
@Override
public void changedConnection(Connection con) {
    super.changedConnection(con);

    if (con.isUp()) {
        DTNHost otherHost = con.getOtherNode(getHost());
        updateDeliveryPredFor(otherHost);
        updateTransitivePreds(otherHost);
    }
}

public double getPredFor(DTNHost host) {
    ageDeliveryPreds();         //make sure preds are updated before getting
    if (preds.containsKey(host)) {
        return preds.get(host);
    } else {
        return 0;
    }
}

2.2.2 因encounter更新

假设节点A与节点B相遇(即连接建立),轮到节点Aupdate,更新的是节点A上的preds(a, b)delivery predictabilities。源代码如下:

//ProphetRouter.java
private void updateDeliveryPredFor(DTNHost host) {
    double oldValue = getPredFor(host);  //取值之前需要更新age
    double newValue = oldValue + (1 - oldValue) * P_INIT;
    preds.put(host, newValue);
}

public double getPredFor(DTNHost host) {
    ageDeliveryPreds();         //make sure preds are updated before getting
    if (preds.containsKey(host)) {
        return preds.get(host);
    } else {
        return 0;
    }
}

2.2.3 因age更新

每隔secondsInTimeUnit(本例为40s),降低所有节点的delivery predictabilities,源代码如下:

//ProphetRouter.java
private void ageDeliveryPreds() {
    double timeDiff = (SimClock.getTime() - this.lastAgeUpdate) / secondsInTimeUnit;
    if (timeDiff == 0) { //如果没超过secondsInTimeUnit,就不更新
        return;
    }

    //所有的节点都乘以GAMMA ^ k
    double mult = Math.pow(GAMMA, timeDiff); //GAMMA ^ k
    for (Map.Entry<DTNHost, Double> e : preds.entrySet()) {
        e.setValue(e.getValue()*mult);
    }

    this.lastAgeUpdate = SimClock.getTime();
}

2.2.4 因transitive更新

transitive更新,有点费解,参考以下的注释:

//ProphetRouter.java    
//updateTransitivePreds(otherHost); 假设a--b,节点a做update,那么下述的host是指b
private void updateTransitivePreds(DTNHost host) {
    MessageRouter otherRouter = host.getRouter();

    double pForHost = getPredFor(host); //P(b,a)
    Map<DTNHost, Double> othersPreds = ((ProphetRouter)otherRouter).getDeliveryPreds();

    for (Map.Entry<DTNHost, Double> e : othersPreds.entrySet()) {
        if (e.getKey() == getHost()) { //此时getHost()是指节点a
            continue; 
        }

        double pOld = getPredFor(e.getKey()); //P(a,c)_old, 实为节点a的getPredFor,相当于this.getPredFor
        double pNew = pOld + ( 1 - pOld) * pForHost * e.getValue() * beta; //e.getValue为P(b, c)
        preds.put(e.getKey(), pNew);
    }
}

2.3 update

ProphetRouter的update在DirectDelivery基础上,调用tryOtherMessages函数,Prophet只将消息发送给delivery predictabilities更高的节点。举例说明,节点A遇到节点B,节点A是否要将消息m(其目的节点为C)复制转发给节点B,答案是若P(b, c)大于P(a, c),那么就将消息m复制转发给B。源代码如下:

//ProphetRouter.java
private Tuple<Message, Connection> tryOtherMessages() {
    List<Tuple<Message, Connection>> messages = new ArrayList<Tuple<Message, Connection>>();
    Collection<Message> msgCollection = getMessageCollection();

    for (Connection con : getConnections()) {
        DTNHost other = con.getOtherNode(getHost());
        ProphetRouter othRouter = (ProphetRouter)other.getRouter();
        if (othRouter.isTransferring()) {
            continue; 
        }

        for (Message m : msgCollection) {
            if (othRouter.hasMessage(m.getId())) {
                continue; 
            }

            // 核心代码
            if (othRouter.getPredFor(m.getTo()) > getPredFor(m.getTo())) { // the other node has higher probability of delivery
                messages.add(new Tuple<Message, Connection>(m,con));
            }
        }
    }

    if (messages.size() == 0) {
        return null;
    }

    //orders the tuples by their delivery probability by the host on the other side of the connection
    Collections.sort(messages, new TupleComparator());

    return tryMessagesForConnected(messages);
}

update函数虽然代码有些长,但最重要的只有两条语句。

专题: DTN路由协议 (5/6)

发表评论

电子邮件地址不会被公开。 必填项已用*标注

11 thoughts on “The ONE使用笔记:Prophet路由

  • 2016年08月08日 星期一 at 08:44下午
    Permalink

    您好,请问一下,您用ONE中默认的配置跑出来prophet的投递率时多少呢

    Reply
    • 2016年08月14日 星期日 at 05:35上午
      Permalink

      抱歉,我不记得我有没有跑过,但刚才看了下我的电脑,没找到。

      Reply
    • 2016年04月06日 星期三 at 03:48下午
      Permalink

      你在实现的时候遇到什么问题以及你所做的哪些努力?

      Reply
      • 2016年04月06日 星期三 at 05:08下午
        Permalink

        就是设计社会性路由算法,在routing目录下,添加java文件,想将社会性加入到算法中,即将区域中的节点划分为不同社区,根据中心度的排名进行信息分配,不知道路由算法中如何实现?

  • 2015年11月15日 星期日 at 10:30上午
    Permalink

    你好,请问一下用one能画出像MATLAB画出的二维坐标图吗?能的话,怎么操作?

    Reply
    • 2015年11月15日 星期日 at 02:13下午
      Permalink

      不行吧。用ONE产生数据,再用其他工具作图,如gnuplot, matplotlib.

      Reply
      • 2015年11月15日 星期日 at 03:40下午
        Permalink

        我听别人说可以安装一个插件,但是不知道是什么插件

  • 2015年09月24日 星期四 at 01:28下午
    Permalink

    你好,我看Prophet源代码的时候看见它还定义了一个私有类TupleComparator 貌似是为了按传输概率大小进行排序。 我不理解为什么要排这个序,因为我是根据节点取出对应的传输概率并不是从头到尾的去传输概率啊。 这里感觉是否多此一举呢?

    Reply
    • 2015年09月24日 星期四 at 05:38下午
      Permalink

      排序的原因是为了选择更好的邻居(根据delivery probability)。“因为我是根据节点取出对应的传输概率并不是从头到尾的去传输概率啊”,很抱歉,不懂你的意思。

      Reply
  • Pingback: The ONE使用笔记:目录 | Spark & Shine