Recent News:

CLWPR description

This page describes the functionality of CLWPR protocol implemented in NS-3 as presented in WNS3 paper. A code review for the module has been opened here.


Overview of NS-3 Routing

The architecture of NS-3 internet stack and routing for IPv4 is described in its manual and represented with Figures 1 and 2 for sending and receiving a message, respectively. Any implementation of a routing protocol in NS-3 should provide two methods declared in ns3::Ipv4RoutingProtocol base class, RouteOutput and RouteInput. The first will provide to the transport protocol a valid route towards the destination for a specific packet. On the other hand, the latter is called by Ipv4L3Protocol when a packet is received from a NetDevice and appropriate action is taken to forward it either to upper layers (local delivery) or to other nodes (forwarding).

ns3-Send ns3-Receive
Figure 1: Flow chart of NS-3 Send Figure 2: Flow chart of NS-3 Receive

CLWPR Specifications

Repositories

  • Neighbor Set: This repository is maintained in order to know the 1-hop neighbors. Each time we receive a "HELLO" message we look into this repository and either update an entry or create a new entry with these elements: Main Address, Interface, Status, Position, Velocity, Heading, RoadID, Utilization, MAC Info, SNIR info, CnF info, Timestamp,and ExpireTime. Each entry will be automatically deleted after a period of 2.5*HelloInterval time in order not to keep neighbors that are not in the vicinity but also hold the information in case a "HELLO" is lost.

  • Position Association Set: This repository keeps track of the position information of any destination that the specific node has data to deliver, a local copy of location service. If there is an entry in this set, that is also a neighbor, it is updated with the "HELLO" messages. Otherwise, a location service - currently the global view of the simulator - will provide this information to maintain the repositor.

Neighbor Discovery

The neighboring discovery mechanism is based on 1-hop periodic broadcast "HELLO" messages. In order to provide position information, navigation information, as well as, cross-layering information, the payload of these "HELLO" messages includes the following node's information: position, velocity, heading, road id, hello interval time, utilization, MAC layer information and number of cached packets from carry-n-forward mechanism. The format of this message is presented below.

		0 bit                  15                        31
		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
		|                                                 |
		|                                                 |
		|        ORIGINATOR POSITION (X,Y)                |
		|                                                 |
		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
		|                                                 |
		|        ORIGINATOR VELOCITY (X,Y)                |
		|                                                 |
		|                                                 |
		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
		|           ORIGINATOR HEADING                    |
		|                                                 |
		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
		|Orig.RoadID |  Htime   |       Utilization       |
		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
		|        Utilization    |        MAC INFO         |
		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
		|         MAC INFO      |    Carry-n-Forward      |
		+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
		

Forwarding

Forwarding in CLWPR is based on minimum weight. A node calculates the weight from the entries it has in its Neighbor Set, for each entry in a node's Position Association Set. Therefore, if a node does not have any entry in Position Association set, it does not have to calculate a routing table which reduces computations. Furthermore, each time one of the two sets is changed, the routing table is recalculated so as to check for new routes the queued packets from the CnF mechanism. The implementation of the table is a std::multimap since we have multiple entries with the same key (Destination Address). The flow charts of the two methods described previously (RouteOutput and RouteInput) are presented below.

  • Route Output
    clwpr-routeOutput
    Figure 3: Flow chart for CLWPR RoutOutput method

  • Route Input
    clwpr-routeInput
    Figure 4: Flow chart for CLWPR RoutInput method

Enhancements

  • Navigation Information

    A special class (ns3::GridMap) has been developed to provide information related to the navigation. The information that is available from this class is the road ID and the calculation of "curvemetic" distance, which is the distance between two nodes following the underlying road topology.


  • Cross-Layering

    Use of cross-layer information from PHY and MAC layers will help select more reliable forwarding nodes. We propose to use the SINR value of the received "HELLO" messages as one metric of link quality. At the end of the receive of each packet, a special tag is attached to it (struct SnrTag : public Tag) which contains the SINR value of that packet. Moreover, we use the MAC layer information regarding the error rate and queueing.


  • Carry-n-Forward

    We address the "local maximum" problem by employing a carry-n-forward mechanism. A special tag is attached to the packets that are faced with local maximum and they are cached localy until a neighbor with less weight is found.

Using CLWPR

CLWPR comes with a helper class (ClwprHelper) that can be used in order to install the routing protocol to the nodes,similar to the implementation of the other IPv4 Routing protocols. Moreover, CLWPR has several attributes that can be used for the configuration and optimization.

Attributes defined for this protocol:

  • HelloInterval: HELLO messages emission interval.
    • Set with class: TimeValue
    • Underlying type: Time
    • Initial value: +1500000000.0ns
    • Flags: construct write read
  • HnaInterval: HNA messages emission interval.
    • Set with class: TimeValue
    • Underlying type: Time
    • Initial value: +5000000000.0ns
    • Flags: construct write read
  • MapFlag: Activate Map Integration
    • Set with class: BooleanValue
    • Underlying type: bool
    • Initial value: false
    • Flags: construct write read
  • EMapFlag: Enchanted Map Integration
    • Set with class: BooleanValue
    • Underlying type: bool
    • Initial value: false
    • Flags: construct write read
  • TxThreshold: Max Tx Range for neighbour selection
    • Set with class: ns3::DoubleValue
    • Underlying type: double
    • Initial value: 500
    • Flags: construct write read
  • PredictFlag: Activate Position Prediction
    • Set with class: BooleanValue
    • Underlying type: bool
    • Initial value: false
    • Flags: construct write read
  • CacheFlag: Activate Carry'n'Forward
    • Set with class: BooleanValue
    • Underlying type: bool
    • Initial value: false
    • Flags: construct write read
  • NormFlag: Normalize the Distance
    • Set with class: BooleanValue
    • Underlying type: bool
    • Initial value: false
    • Flags: construct write read
  • MaxQueueLen: Maximum number of packets that we allow a routing protocol to buffer.
    • Set with class: ns3::UintegerValue
    • Underlying type: uint32_t
    • Initial value: 50
    • Flags: construct write read
  • MaxQueueTime: Maximum time packets can be queued (in seconds)
    • Set with class: TimeValue
    • Underlying type: Time
    • Initial value: +10000000000.0ns
    • Flags: construct write read
  • DistFact: Distance Weighting Factor
    • Set with class: ns3::DoubleValue
    • Underlying type: double
    • Initial value: 1
    • Flags: construct write read
  • AngFact: Angle Weighting Factor
    • Set with class: ns3::DoubleValue
    • Underlying type: double
    • Initial value: 1
    • Flags: construct write read
  • UtilFact: Utilazation Weighting Factor
    • Set with class: ns3::DoubleValue
    • Underlying type: double
    • Initial value: 1
    • Flags: construct write read
  • MACFact: MAC Frame Error Rate Weighting Factor
    • Set with class: ns3::DoubleValue
    • Underlying type: double
    • Initial value: 1
    • Flags: construct write read
  • CnFFact: Carry-N-Forward Weighting Factor
    • Set with class: ns3::DoubleValue
    • Underlying type: doubl
    • Initial value: 1
    • Flags: construct write read
  • SNRFact: SNIR Weighting Factor
    • Set with class: ns3::DoubleValue
    • Underlying type: double
    • Initial value: 1
    • Flags: construct write read
  • RoadFact: Road Relevance Weighting Factor
    • Set with class: ns3::DoubleValue
    • Underlying type: double
    • Initial value: 1
    • Flags: construct write read
  • RoadMap: Road Map pointer
    • Set with class: ns3::PointerValue
    • Underlying type: ns3::Ptr<ns3::GridMap >
    • Initial value: 0
    • Flags: construct write

TraceSources defined for this type:

  • Rx: Receive CLWPR packet.
  • Tx: Send CLWPR packet.
  • RoutingTableChanged: The CLWPR routing table has changed.
  • CarryNForward: A packet has been queued due to local maximum
  • Dequeue: A packet has been dequeued from local maximum
  • DropCache: Drop a cached packet

Comparison with other protocols

The comparison of CLWPR with AODV, OLSR and DSDV shows that the proposed protocol has higher packet delivery ratio, lower simulation time and relatively low end-to-end delay.

ns3-pdr ns3-e2ed
Figure 5: PDR Figure 6: End-to-End Delay
ns3-time
Figure 5: Elapsed time