Click here to Skip to main content
Click here to Skip to main content

Tagged as

Entropy based Multipath Routing for Mobile Adhoc network in Omnet++

, 9 Oct 2011 CPOL
Rate this:
Please Sign up or sign in to vote.
This is a simulation model demonstrating the working of Multipath MANET routing with Entropy as cost Metric

download Source Code 

http://grasshoppernetwork.com/Technical/Share/Entropy.zip 

A wireless ad hoc network is a collection of two or more devices with wireless communications and networking capabilities that communicate with each other without the aid of any centralized administrators. The network topology is dynamic, because the connectivity among the nodes may vary with time due to node mobility, departures and new arrivals. Hence, the need for efficient routing protocols to allow the nodes to communicate.

In a network with shared resources, where multiple senders compete for link bandwidth, it is necessary to adjust the data rate used by each sender in order not to overload the network. Packets that arrive at a router and cannot be forwarded are dropped, consequently an excessive amount of packets arriving at a network bottleneck leads to many packet drops. These dropped packets might already have travelled a long way in the network and thus consumed significant resources. Additionally, the lost packets often trigger retransmissions, which mean that even more packets are sent into the network. Thus network congestion can severely deteriorate network throughput. If no appropriate congestion control is performed this can lead to a congestion collapse of the network, where almost no data is successfully delivered.

Main Reasons for Congestion as given below

  1. New route incorporates a node which is already part of other routes and is overloaded with traffic( Network Layer)
  2. Application or channel data rate is more than MAC layer Queue size ( Congestion at MAC layer)
  3. Many nodes in a neighborhood fights for channel slots( Contention problem of MAC Layer)
  4. Packets suffer immense power loss due to noise in the channel and it triggers multiple retransmission(Physical layer congestion problem)
  5. Nodes which had enough bandwidth at the time of forming the route are overburdened with Traffic( Network layer Congestion Problem)
  6. Conventional TCP triggering false retransmission due to delayed delivery of packets( TCP congestion problem)
  7. Route maintenance control packets are over flooded, causing immense bandwidth consumption ( Control Overhead Related Congestion Problem at either MAC or Routing Layer)
  8. Various types of traffics have different priorities. Priority traffic when allocated bandwidth with the same fairness principal to normal traffic, and they are delayed, it triggers dropping those packets even after successful transmission. ( Congestion due to lack of fairness in channel allocation by either MAC layer or by network layer)
  9. Interference in the channel and multipath fading makes the same signal arrive at a node from different direction and at different interval causing substantial delay in completing reception( Congestion due to interference)

Parameters Related to Congestion Control in MANET

Parameters

  1. Bandwidth
  2. Delay
  3. Control overhead
  4. SNR
  5. BER
  6. Contention Window
  7. Back off Timer
  8. Link Speed
  9. MAC Queue
  10. Frequency and Time Slots
  11. Network Layer Queue
  12. Priority and Traffic types
  13. Power and Energy
  14. Fading and Link loss
  15. Transport layer Window
  16. Throughput
  17. Probability Matrices
  18. Position of the Nodes and Interference

It is difficult to elaborate the role and significance of the parameters towards causing the congestion. At different instances, different parameters plays different role in causing the congestion. Therefore it is important to consider important factors from each of network layer, MAC layer, and Physical layer for suitably designing a congestion free MANET communication. But incase multiple parameters are chosen, their significance is impossible to be determined. Therefore a better solution is to combine the affect of the parameters such that the cost generated out of all the parameters can be considered for Routing or Scheduling or Load Balancing. As the parameters at different stages have different values and the range is difficult to be determined sometime, it is important to consider the state of the parameters rather than the value. Hence A Entropy measurement out of all the considered parameters is better Suited.

Proposed Technique

Parameters

  • NP1, MP2, PP3 (Are network, Mac and Physical layer Parameters)
  • MP2: Probability of Channel State Observation
Current State Next State Total
Free Busy
Busy Busy
Busy Free
Free Free

PP3: Bit Error Probability (Total Numbers of Bits Erroneous at a Measurement Instance)

NP1: Data Bandwidth Ration (Ratio of Available bandwidth for Data/Used Bandwidth for Control)

In this project we propose joint entropy based routing for congestion control. We considered three parameters bit error, channel state, data bandwidth ratio .we use entropy as a measure of local information available to every node. The results demonstrate that information captured through entropy is very effective in congestion control.

Source node broadcast the route request RREQ. The intermediate node calculates their joint entropy and appends its entropy value to the RREQ and forwarded. the destination node checks the time stamp of RREQ, if less than threshold then it will calculates the total entropy of that path. Destination node appends the total entropy of that path to RREP. When the RREP reach to source, it will send the packets through that path.

There is more than one path through the intermediate node from source to destination. The intermediate node schedule the packets to high entropy path first and then low entropy path for utilize the resource maximum.

The following are steps of proposed technique

Step1: finding joint entropy of channel state, bit error rate, data bandwidth ratio.

Bit error rate entropy is calculated as follow

  1. Take BER value from physical layer
  2. Classify as high, low, medium
  3. Check how much low, high, medium reading are there
BER_entropy= -1*(s1/sum*log(s1/sum)+s2/sum*log(s2/sum)+s3/sum*log(s3/sum))
//s1/sum,s2/sum and s3/sum gives the probability values

Data bandwidth ratio entropy is calculated as follows

  1. Calculate the BwF = ratio of available bandwidth for data/used bandwidth for control
  2. Classify as low, high, medium
  3. Check how many low, high and medium readings.
BwF_entropy=-1*(s1/sum*log(s1/sum)+s2/sum*log(s2/sum)+s3/sum*log(s3/sum))
//s1/sum,s2/sum and s3/sum gives the probability values

Channel state entropy is calculated as follows

  1. Caluclate the channel state from Mac layer.
  2. Classify channel state as current state and next state.
  3. The channel can be in one of following states.

Current State

Next State

Free

Busy

Busy

Busy

Busy

Free

Free

Busy

4. Probability of channel state is calculated

Entropy of channel is calculated as follows.

Ch_entropy= -1*(s1/sum*log (s1/sum)+s2/sum*log(s2/sum)+s3/sum*log(s3/sum)+s4/sum*log(s4/sum))

The joint entropy as follows

Joint Entropy = Ch_entropy + BwF_entropy+ber_entropy

Step 2: Multiple Paths

  1. Sender floods the RREQ which contain additional fields of joint entropy of(ber,bwr,channel state).each node calculates joint entropy and appends in RREQ.
  2. If the intermediate node having joint entropy value greater than threshold discard RREQ packet.
  3. Destination node calculates the total cost of joint entropy.
  4. Destination generates the n no of RREP where n is the no of paths.

Step 3: generating RERR packet

  1. Every packet (control & data) contain time stamp value
  2. During transmission if delay>threshold

Generate RERR drop the path

Delay=received time-sent time

Implementation Overview

Calculation of Parameters

1. In MAC Layer, Channel State is calculated as shown below.

void SimpleMac::handleMessage(cMessage* msg)
{
    d("handle");
    //send the messages to the neighbours
    if ( msg->arrivedOn("fromRoute") )
    {
        d("msg from Route");

        //the message will be deleted by the physic
        //module
        send(msg,"toPh");
    }
    else
    //if the router has finished his work,send another message
    if (msg == endService)
    {
        d("end service");
        if(!buffer->empty())
        {
            //send up a waiting message
            cMessage* m = buffer->pop();
            Bandwidth=Bandwidth+m->length();
            send(m, "toRoute");
            // FIXME it is illegal to send a msg
            // object and keep referencing it!!! -Andras
     
                scheduleAt(elabTime(m) ,endService);
        }
        else
        {
            //set the host as idle
            d("no messages...waiting");
            routerBusy = false;
        }
    }
    else
    {
        //send to higher levels... if....
        if( ( (int)msg->par("mac") != parentModule()->id() ) &&
            ( (int)msg->par("mac") != BROADCAST ) &&
            ( ! promisqueMode) )
        {
            d("message not for this node,discarding");
            delete msg;
        }
        else
        {
            //this node can handle the message
            d("got message from "<<msg->par("source"));
            //if the host was idle
            if( (!routerBusy) && (buffer->empty()) )
            {
                routerBusy = true;
                // FIXME it is illegal to send a msg object
                // and keep referencing it!!! -Andras
                    send(msg,"toRoute");
                    scheduleAt( elabTime(msg), endService);
            }
            else
            {
                if(buffer->canStore(msg->length()))
                {
                    d("host busy, will put the msg in the buffer!");
                    buffer->insert(msg);
                    Bandwidth=Bandwidth-msg->length();
     
                }
                else
                {
                    d("input buffer full!!! discarding pkts");
                    bufferFullDiscard++;
                    delete msg;
                }
            }
        }
    }
    if(lastState==-1)
    {
        lastState=(int)routerBusy;
    }
    else
    {
        int currentState=(int)routerBusy;
        ChState[currentState][lastState]++;
        lastState=currentState;
        ev<<" @ Node" <<parentModule()->id()-2<<" States are\n";
        ev<<"FREE->FREE"<<ChState[0][0]<<"\n";
        ev<<"FREE->BUSY"<<ChState[0][1]<<"\n";
        ev<<"BUSY->FREE"<<ChState[1][0]<<"\n";
        ev<<"BUSY->BUSY"<<ChState[1][1]<<"\n";
    }
}

2. In Routing Layer, Bandwidth Ratio is calculated

a) When a Node handle Control Message TotControl is incremented

void aodv::handleMessage(cMessage *msg)
{
    cMessage* reply = NULL;
    d("HANDLE message routine");
    if (msg->arrivedOn("fromApp") )
    {
        d("messasge arrived from app");
        reply = sendData(msg);
        broadcast(reply);
        delete msg;
    }
    else
    {
        //collect the message kind
        pktHistogram.collect( msg->kind() );
        switch(msg->kind())
        {
            case MK_SEND_HELLO:
                 d("sendHello");
                 reply = generateHELLOmsg();
                 broadcast(reply);
                 TotControl++;
                 break;
            case MK_DELETE:
                 /*
                  * Note that the Lifetime field in the
                  * routing table plays a dual role
                  *  -- for an active route it is the
                  *  expiry time, and for an invalid
                  *  route it is the deletion time.
                 *  If a data packet is received for an
                  *  invalid route, the Lifetime field is
                  *  updated to current time plus
                  *  DELETE_PERIOD.
                  */
                d("delete");
                 reply = handleDelete(msg);
                 broadcast(reply);
                 break;
            case HELLO:
                d("hello");
                 //aodv specification says that the HELLO messages
                 //are a spcial kind of RREP msg.
                 //For semplicity I've chosen to treat
                 //them as a different kind of message.
                 handleHELLO(msg);
                 delete msg;
                 break;
            case MK_FLUSH:
                d("flush");
                 //A RREQ has been timed out
                 //so do what has to be done
                 reply = handleFlush(msg);
                 broadcast(reply);
                 break;
            case RREQ:
                 d("RREQ "<<msg->name());
                 reply = handleRREQ(msg);
                 //if the message received need a reply
                 //then send it to the mac module that will
                 //care about sending it around
                 broadcast(reply);
                 TotControl++;
                 delete msg;
                 break;
            case RREP:
                d("RREP");
                reply = handleRREP(msg);
                broadcast(reply);
                TotControl++;
                delete msg;
                break;
            case RERR:
                d("RERR");
                reply = handleRERR(msg);
                broadcast(reply);
                delete msg;
                TotControl++;
                break;
            case DATA:
                d("data");
                reply = handleData(msg);
                
                broadcast(reply);
                delete msg;
                break;
            case RREP_ACK:
                d("ack");
                handleACK(msg);
                delete msg;
                TotControl++;
                break;
            case MK_ESP_ACK:
                d("esp_ack");
                reply = handleESP_ACK(msg);
                broadcast(reply);
                break;
            case MK_BLK_LIST:
                d("black list");
                handleBLK_LIST(msg);
                delete msg;
                break;
        }
    }
}

b) Bandwidth is Updated @ MAC Layer

if(!buffer->empty())
    {
        //send up a waiting message
        cMessage* m = buffer->pop();
        Bandwidth=Bandwidth+m->length();
        // FIXME it is illegal to send a msg object and keep 
        // referencing it!!! -Andras
        send(m, "toRoute");
        scheduleAt(elabTime(m) ,endService);
    }
    else
    {
        //set the host as idle
        d("no messages...waiting");
        routerBusy = false;
    }
}
else
{
    //send to higher levels... if....
    if( ( (int)msg->par("mac") != parentModule()->id() ) &&
        ( (int)msg->par("mac") != BROADCAST ) &&
        ( ! promisqueMode) )
    {
        d("message not for this node,discarding");
        delete msg;
    }
    else
    {
        //this node can handle the message
        d("got message from "<<msg->par("source"));
        //if the host was idle
        if( (!routerBusy) && (buffer->empty()) )
        {
            routerBusy = true;
            // FIXME it is illegal to send a msg object
            // and keep referencing it!!! -Andras
            send(msg,"toRoute");
            scheduleAt( elabTime(msg), endService);
        }
        else
        {
            if(buffer->canStore(msg->length()))
            {
                d("host busy, will put the msg in the buffer!");
                buffer->insert(msg);
                Bandwidth=Bandwidth-msg->length();
            }
            else
            {
                d("input buffer full!!! discarding pkts");
                bufferFullDiscard++;
                delete msg;
            }
        }

c) Both information’s are used to calculate Final matrix

In HandleRREQ:

BAND_RATIO=mac->Bandwidth/TotControl;
ev<<" @ NODE "<<parentModule()->id()-2
  <<" BANDWIDTH for DATA="<<mac->Bandwidth
  <<" CONTROL BANDWIDTH="<<TotControl
  <<" RATIO="<<BAND_RATIO<<"\n";

3. Bit Error Probabiloity is Calculated at the Physical layer

d("msg from outside");
        if(msg->hasBitError())
{
    d("received message with errors...discarding!");
    msgWithErr++;
    delete msg;
}

Entropy calculation

void aodv::UpdateEntropy()
{
    /////////////////////// STATE CALCULATION////////////////////////
    int ber=phy->msgWithErr;
    int ber_state=0; //0 for low 1 for mediam 2 for high
    if(ber<5)
    {
        ber_state=0;
    }
    if(ber>=5 && ber<10)
    {
        ber_state=1;
    }
    if(ber>15)
    {
        ber_state=2;
    }
    statesBER[ber_state][current]++; 
    int bw_state=0;
    if(BAND_RATIO<400000)
    {
        bw_state=2;
    }
    if(BAND_RATIO>=400000 && BAND_RATIO<800000)
    {
        bw_state=1;
    }
    if(BAND_RATIO>800000)
    {
        bw_state=0;
    }
    statesBwF[bw_state][current]++; 
    current++;
    if(current>=4)
    {
        current=0;
    }
    ev<<" FOR ENTROPY CURRENT STATES OF BW IS "
      <<bw_state<<" BER STATE IS"<<ber_state<<"\n";
    ////////////////////////////ENTROPY CALCULATION////////////////////
    double ber_entropy=0;
    double sum=0.0;
    double s3,s1,s2;
    for(int i=0;i<4;i++)
    {
        s3=statesBER[0][i];
        sum=sum+s3;
        s1=statesBER[1][i];
        sum=sum+s1;
        s2=statesBER[2][i];
        sum=sum+s2;
    }
    //s1/sum,s2/sum and s3/sum gives the probability values
    ber_entropy=-1*(s1/sum*log(s1/sum)+s2/sum*log(s2/sum)+s3/sum*log(s3/sum));
    ev<< "BER ENTROPY="<<ber_entropy<<"\n";
    ///////BWF ENTROPY///////////////////////////
    double BwF_entropy=0;
    sum=0.0;

    for(int i=0;i<4;i++)
    {
        s3=statesBwF[0][i];
        sum=sum+s3;
        s1=statesBwF[1][i];
        sum=sum+s1;
        s2=statesBwF[2][i];
        sum=sum+s2;
    }
    //s1/sum,s2/sum and s3/sum gives the probability values
    BwF_entropy=-1*(s1/sum*log(s1/sum)+s2/sum*log(s2/sum)+s3/sum*log(s3/sum));
    ev<< "BwF ENTROPY="<<BwF_entropy<<"\n";
    /////////////////CHANNEL STATE ENTROPY///////////////////////////////////////////
    sum=0;
    sum=sum+mac->ChState[0][0];
    sum=sum+mac->ChState[0][1];
    sum=sum+mac->ChState[1][0];
    sum=sum+mac->ChState[1][1];
    double s4;
    s1=mac->ChState[0][0];
    s2=mac->ChState[0][1];
    s3=mac->ChState[1][0];
    s4=mac->ChState[1][1];
    double ch_entropy=
      -1*(s1/sum*log(s1/sum)+s2/sum*log(s2/sum)+
      s3/sum*log(s3/sum)+s4/sum*log(s4/sum));
    ev<< "Channel STate ENTROPY="<<ch_entropy<<"\n";
    /////////////////////////////JOINT ENTROPY/////////////////////////////
    jointEp=ch_entropy+BwF_entropy+ber_entropy;
    ev<< "JOINT ENTROPY="<<jointEp<<"\n";
}

The above function is called from within handleMessage function

Put entropy info in RREQ

cMessage* aodv::generateRREQmsg(RouteTableElement* e,int dest,int ttl)
{
    cMessage* reply = new cMessage("RREQ",RREQ,CTRL_PKT_SIZE,P_RREQ);
    d("genRREQ");
    reply->addPar("originator") = parentModule()->id();
    reply->addPar("dest") = dest;
    reply->addPar("seqNumS") = sequenceNumber++;
    reply->addPar("seqNumD") = (e == NULL? 0 : e->seqNum);
    reply->addPar("reqId") = reqId++;
    reply->addPar("hopCount") = 0;
    reply->addPar("ttl") = ttl;
    reply->addPar("mac") = BROADCAST;

    reply->addPar("Entropy")=jointEp;

    int k=0;

    char s[10];
    itoa(k,s,10);
    reply->addPar(s)=parentModule()->id()-2;
    k++;
    itoa(k,s,10);
    reply->addPar("tot")=k;
    reply->addPar("Delay")=0;
    return reply;
}

Each node puts its entropy info once it receives RREQ

double ep=(double)msg->par("Entropy");
ep=ep+jointEp;
msg->par("Entropy")=ep;

Append this entropy information in RREP

cMessage* aodv::generateRREPmsg(cMessage* msg, int seqNumD,int hops)
{
    cMessage* RREP = new cMessage("RREP",RREP,CTRL_PKT_SIZE,P_RREP);
    d("genRREP");
    //spcify the node addtess for wich a route
    //is supplyed
    RREP->addPar("dest") = msg->par("dest");
    //the destination seqNum associated to
    //the route
    RREP->addPar("seqNumD") = seqNumD;
    //RREP.originator is the address of the
    //node which originated the RREQ
    RREP->addPar("originator") =(int)  msg->par("originator");
    //the time for wich nodes receiving the RREP cosider
    //the route to be valid
    RREP->addPar("lifetime") = MY_ROUTE_TIMEOUT;
    //if the node is the destinatary of the RREQ then hopcount is 0
    //otherwise it is the distance to the destination
    RREP->addPar("hopCount")=0;
    //ask for a RREP-ACK. used for unidir.links
    RREP->addPar("flagA") = 1;
    RREP->addPar("seqNumS") = sequenceNumber;
    RREP->addPar("ttl") = hops ;
    RREP->addPar("mac") = msg->par("source");
    RREP->addPar("Entropy")=pathEntropy;
    return RREP;
}

When RREP is reached at an Intermediate Node, It notes down the values in handleRREP function

///////////////////////////////////Intermediate node notes the entropy info////////////
Routes[ri].src=(int)msg->par("originator");
Routes[ri].dst=(int)msg->par("dst");
Routes[ri].Entropy=(double)msg->par("Entropy");
ri++;
///////////////////////////////////////////////////////////

Take the Scheduling Decision based on entropy value.

If (entropy>5)
    Schedule first
Else
    Schedule late
In handleData message
    d("Data message updated, forwarding!");

reply = copyMessage(msg);
reply->par("mac") = e->nextHop;
///////////// First Search the Entropy of the path...
// if its low, schedule late else schedule first
double mye=0;
int s=(int)msg->par("originator");
int d=(int)msg->par("dest");
for(int i=0;i<ri;i++)
{
    if(Routes[i].src==s && Routes[i].dst==d)
    {
        mye=Routes[i].Entropy;
    }
}
if(mye<5)
{
    ev<<"DATA ARRIVED AT NODE "<<parentModule()->id()-2
      <<" FOR DESTINATION"<<d<<" ENTROPY is "
      <<mye<<"ITS LOW SO SCHEDULE LATE\n";
}
else
{
    ev<<"DATA ARRIVED AT NODE "<<parentModule()->id()-2
      <<" FOR DESTINATION"<<d<<" ENTROPY is "
      <<mye<<"ITS HIGH  SO SCHEDULE FIRST\n";
}
////////////////////////////////////////////////////////////////////////
/*Perkins....
 * Each time a route is used to forward a data packet,
  its Active Route Lifetime field of both the destination and the
  next hop on the path to the destination is updated to be no
  less than the current time plus ACTIVE_ROUTE_TIMEOUT.
*/
e->expiration = max(e->expiration,simTime() +ACTIVE_ROUTE_TIMEOUT);
//shift the invalidation of the route
cancelEvent(e->deleteMessage);
scheduleAt( e->expiration, e->deleteMessage);
e = findNode(e->nextHop);
e->expiration = max(e->expiration,simTime() +ACTIVE_ROUTE_TIMEOUT);
if(mye>5.0)
{
    // Increase active life of the message
    e->expiration=e->expiration+2.0;
}
//shift the invalidation of the route
cancelEvent(e->deleteMessage);
scheduleAt(e->expiration, e->deleteMessage);
return reply;

System Requirements

  1. omnet++ 3.3 p1
  2. Visual Studio .NET 2005/2008

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

integrated ideas
CEO Integrated Ideas
India India
I am the founder and CEO of an startup company http://www.grasshoppernetwork.com , a Knowledge sharing portal for intellects. I have developed various applications and web based and stand alone projects in C#.Net, Omnet++, Java, Matlab, VHDl,OpenCV.

Comments and Discussions

 
Questionrequest PinmemberMember 1036689119-Feb-14 21:08 
QuestionGood article PinmemberFrancisco Alvarez27-Feb-13 9:50 
AnswerRe: Good article PingroupGrasshopper.iics1-Mar-13 13:48 
GeneralRe: Good article PinmemberFrancisco Alvarez4-Mar-13 13:29 
GeneralRe: Good article PingroupGrasshopper.iics4-Mar-13 13:51 
GeneralRe: Good article PinmemberFrancisco Alvarez4-Mar-13 15:00 
QuestionThank you code project Pinmemberintegrated ideas9-Oct-11 22:49 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.141220.1 | Last Updated 10 Oct 2011
Article Copyright 2011 by integrated ideas
Everything else Copyright © CodeProject, 1999-2014
Layout: fixed | fluid