DirectDelivery和Epidemic是两种极端，前者，从不复制，只有碰到目的节点，才交付信息；后者，将消息复制给碰到的节点。路由协议设计核心是如何让投递率（delivery probability）接近Epidemic，同时让开销尽可能的小，即选择哪些消息传递给哪些节点。本文介绍Spray and Wait路由。

1. 路由策略

介绍Spray and Wait路由的文章如下：

SPYROPOULOS, Thrasyvoulos, PSOUNIS, Konstantinos, et RAGHAVENDRA, Cauligi S. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In : Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking. ACM, 2005. p. 252-259. BibTex

相对于Epidemic，SprayAndWait降低消息在网络中的份数，即对复制次数做一些限制。正如其名，SprayAndWait包含两个阶段（假设每个消息初始化为L copies，即网络中含有某消息最多L份）：

• Spray：当碰到一个节点时，决定多少份给该节点。最简单的分发策略是一份一份地发；还有另一种分发策略是每次将一半copies给遇到的节点（Binary Spray and Wait），当节点只有一份消息时，就退化成DirectDelivery了
• Wait：只要copies大于1，就将消息分给碰到的节点，直到1。当节点只有一份的时候，就等待碰到目的节点（想想DirectDelivery）

论文证明了减半分发（Binary Spray and Wait）是最优的（the minimum expected delay）。确切地说，节点A有n copies，遇到节点B，此时将n/2 copies（上取整）给B，节点A留下n/2 copies（下取整）。

2. SprayAndWait

2.1 设置文件

由上述分析可知，SprayAndWait需要事先知道消息的份数以及分发策略，相关设置字段如下：

//*_settings.txt
Group.router = SprayAndWaitRouter
SprayAndWaitRouter.nrofCopies = 10      //消息的份数
SprayAndWaitRouter.binaryMode = true    //true为一半一半地分，false为一份一份地分

//SprayAndWaitRouter.java
public static final String NROF_COPIES = "nrofCopies"; //identifier for the initial number of copies setting
public static final String BINARY_MODE = "binaryMode"; //identifier for the binary-mode setting
public static final String SPRAYANDWAIT_NS = "SprayAndWaitRouter";  //SprayAndWait router's settings name space

public SprayAndWaitRouter(Settings s) {
    super(s);
    Settings snwSettings = new Settings(SPRAYANDWAIT_NS);
    initialNrofCopies = snwSettings.getInt(NROF_COPIES);
    isBinary = snwSettings.getBoolean( BINARY_MODE);
}

2.2 增加消息字段

每个消息需要一个字段保存份数copies，因此，需要为Message添加新的字段。我之前的做法是直接修改Message类，今天看了SprayAndWaitRouter.java的源码，原来还可以这样：重写createNewMessage，在原来基础上利用函数msg.addProperty添加字段。源代码如下：

//SprayAndWaitRouter.java    
@Override
public boolean createNewMessage(Message msg) {
    makeRoomForNewMessage(msg.getSize());
    
    msg.setTtl(this.msgTtl);
    msg.addProperty(MSG_COUNT_PROPERTY, new Integer(initialNrofCopies)); //添加字段
    addToMessages(msg, true);
    return true;
}

//MSG_COUNT_PROPERTY为SprayAndWaitRouter.copies
public static final String MSG_COUNT_PROPERTY = SPRAYANDWAIT_NS + "." +    "copies"; 

取得和更新该字段值的方法如下（可参见下面的getMessagesWithCopiesLeft函数）：

Integer nrofCopies = (Integer)m.getProperty(MSG_COUNT_PROPERTY); //取值
msg.updateProperty(MSG_COUNT_PROPERTY, nrofCopies);              //更新

2.3 update

SprayAndWait的update函数很简单，类似于Epidemic的tryAllMessagesToAllConnections，但更严格，即消息队列过滤掉那些copies为1的消息。源代码如下：

//SprayAndWaitRouter.java
public void update() {
    super.update();
    if (!canStartTransfer() || isTransferring()) {
        return; 
    }
    if (exchangeDeliverableMessages() != null) {
        return;
    }

    //获取缓冲区有效消息集合，即copies大于1的消息
    List<Message> copiesLeft = sortByQueueMode(getMessagesWithCopiesLeft());
    if (copiesLeft.size() > 0) {
        this.tryMessagesToConnections(copiesLeft, getConnections());
    }
}

2.3.1 getMessagesWithCopiesLeft

getMessagesWithCopiesLeft在getMessageCollection()的基础上，过滤掉那些copies小于1的消息，源代码如下：

//SprayAndWaitRouter.java
protected List<Message> getMessagesWithCopiesLeft() {
    List<Message> list = new ArrayList<Message>();
    for (Message m : getMessageCollection()) {
        Integer nrofCopies = (Integer)m.getProperty(MSG_COUNT_PROPERTY);
        assert nrofCopies != null : "SnW message " + m + " didn't have " + "nrof copies property!";
        if (nrofCopies > 1) {
            list.add(m);
        }
    }
    return list;
}

2.4 更新消息的份数

假设A发送消息m给B，那么传输完毕后，A和B的缓冲区都有m，都需要对m更新copies。值得注意的是，更新发送端和接收端都由A发起，源代码如下：

//ActiveRouter.java
public void update() {
    super.update();
    ...
    if (con.isMessageTransferred()) {  //消息是否传输完毕，即是否过了(1.0*m.getSize())/this.speed没
        if (con.getMessage() != null) {
            transferDone(con);       //更新发送端
           con.finalizeTransfer();    //更新接收端
        }
    }
    ...
}

//Connection.java    更新接收端
public void finalizeTransfer() {
    this.bytesTransferred += msgOnFly.getSize();
    getOtherNode(msgFromNode).messageTransferred(this.msgOnFly.getId(), msgFromNode); //更新接收端
    clearMsgOnFly();
}

2.4.1 更新发送端

//SprayAndWaitRouter.java
@Override
protected void transferDone(Connection con) {
    //步骤1：取得消息的copies
    Integer nrofCopies;
    String msgId = con.getMessage().getId();
    Message msg = getMessage(msgId);
    if (msg == null) {
        return; 
    }
    nrofCopies = (Integer)msg.getProperty(MSG_COUNT_PROPERTY);
    
    //步骤2：更新消息的copies
    if (isBinary) {
        nrofCopies /= 2;
    } else {
        nrofCopies--;
    }
    msg.updateProperty(MSG_COUNT_PROPERTY, nrofCopies);
}

2.4.2 更新接收端

//SprayAndWaitRouter.java  
@Override
public Message messageTransferred(String id, DTNHost from) {
    Message msg = super.messageTransferred(id, from);
    
    //步骤1：取得消息的copies
    Integer nrofCopies = (Integer)msg.getProperty(MSG_COUNT_PROPERTY);
    assert nrofCopies != null : "Not a SnW message: " + msg;

    //步骤2：更新消息的copies
    if (isBinary) {
        nrofCopies = (int)Math.ceil(nrofCopies/2.0);
    } else {
        nrofCopies = 1;
    }
    msg.updateProperty(MSG_COUNT_PROPERTY, nrofCopies);
    
    return msg;
}

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

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

赞赏

微信赞赏支付宝赞赏