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部分，公式如下：

（1）encounter

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

（2）age

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

（3）transitive

考虑节点间的传递性，如节点A经常遇到节点B，B经常遇见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 何时更新

对于encounter和transitive，当链接建立时更新；对于age，每隔secondsInTimeUnit更新一次。值得注意的是，更新age比较被动。updateDeliveryPredFor和updateTransitivePreds都会调用getPredFor，取得节点的delivery predictabilities，getPredFor函数会调用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相遇（即连接建立），轮到节点A做update，更新的是节点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)

• The ONE使用笔记：DirectDelivery路由
• The ONE使用笔记：Epidemic路由
• The ONE使用笔记：SprayAndWait路由
• The ONE使用笔记：MaxProp路由
• The ONE使用笔记：Prophet路由
• The ONE使用笔记：实现Bubble Rap

赞赏

微信赞赏支付宝赞赏