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
- New route incorporates a node which is already part of other routes and is overloaded with traffic( Network Layer)
- Application or channel data rate is more than MAC layer Queue size ( Congestion at MAC layer)
- Many nodes in a neighborhood fights for channel slots( Contention problem of MAC Layer)
- Packets suffer immense power loss due to noise in the channel and it triggers multiple retransmission(Physical layer congestion problem)
- Nodes which had enough bandwidth at the time of forming the route are overburdened with Traffic( Network layer Congestion Problem)
- Conventional TCP triggering false retransmission due to delayed delivery of packets( TCP congestion problem)
- Route maintenance control packets are over flooded, causing immense bandwidth consumption ( Control Overhead Related Congestion Problem at either MAC or Routing Layer)
- 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)
- 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
- Bandwidth
- Delay
- Control overhead
- SNR
- BER
- Contention Window
- Back off Timer
- Link Speed
- MAC Queue
- Frequency and Time Slots
- Network Layer Queue
- Priority and Traffic types
- Power and Energy
- Fading and Link loss
- Transport layer Window
- Throughput
- Probability Matrices
- 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
- Take BER value from physical layer
- Classify as high, low, medium
- 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
- Calculate the BwF = ratio of available bandwidth for data/used bandwidth for control
- Classify as low, high, medium
- 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
- Caluclate the channel state from Mac layer.
- Classify channel state as current state and next state.
- 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
- 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.
- If the intermediate node having joint entropy value greater than threshold discard RREQ packet.
- Destination node calculates the total cost of joint entropy.
- Destination generates the n no of RREP where n is the no of paths.
Step 3: generating RERR packet
- Every packet (control & data) contain time stamp value
- 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");
if ( msg->arrivedOn("fromRoute") )
{
d("msg from Route");
send(msg,"toPh");
}
else
if (msg == endService)
{
d("end service");
if(!buffer->empty())
{
cMessage* m = buffer->pop();
Bandwidth=Bandwidth+m->length();
send(m, "toRoute");
scheduleAt(elabTime(m) ,endService);
}
else
{
d("no messages...waiting");
routerBusy = false;
}
}
else
{
if( ( (int)msg->par("mac") != parentModule()->id() ) &&
( (int)msg->par("mac") != BROADCAST ) &&
( ! promisqueMode) )
{
d("message not for this node,discarding");
delete msg;
}
else
{
d("got message from "<<msg->par("source"));
if( (!routerBusy) && (buffer->empty()) )
{
routerBusy = true;
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
{
pktHistogram.collect( msg->kind() );
switch(msg->kind())
{
case MK_SEND_HELLO:
d("sendHello");
reply = generateHELLOmsg();
broadcast(reply);
TotControl++;
break;
case MK_DELETE:
d("delete");
reply = handleDelete(msg);
broadcast(reply);
break;
case HELLO:
d("hello");
handleHELLO(msg);
delete msg;
break;
case MK_FLUSH:
d("flush");
reply = handleFlush(msg);
broadcast(reply);
break;
case RREQ:
d("RREQ "<<msg->name());
reply = handleRREQ(msg);
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())
{
cMessage* m = buffer->pop();
Bandwidth=Bandwidth+m->length();
send(m, "toRoute");
scheduleAt(elabTime(m) ,endService);
}
else
{
d("no messages...waiting");
routerBusy = false;
}
}
else
{
if( ( (int)msg->par("mac") != parentModule()->id() ) &&
( (int)msg->par("mac") != BROADCAST ) &&
( ! promisqueMode) )
{
d("message not for this node,discarding");
delete msg;
}
else
{
d("got message from "<<msg->par("source"));
if( (!routerBusy) && (buffer->empty()) )
{
routerBusy = true;
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()
{
int ber=phy->msgWithErr;
int ber_state=0; 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";
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;
}
ber_entropy=-1*(s1/sum*log(s1/sum)+s2/sum*log(s2/sum)+s3/sum*log(s3/sum));
ev<< "BER ENTROPY="<<ber_entropy<<"\n";
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;
}
BwF_entropy=-1*(s1/sum*log(s1/sum)+s2/sum*log(s2/sum)+s3/sum*log(s3/sum));
ev<< "BwF ENTROPY="<<BwF_entropy<<"\n";
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";
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");
RREP->addPar("dest") = msg->par("dest");
RREP->addPar("seqNumD") = seqNumD;
RREP->addPar("originator") =(int) msg->par("originator");
RREP->addPar("lifetime") = MY_ROUTE_TIMEOUT;
RREP->addPar("hopCount")=0;
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
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;
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";
}
e->expiration = max(e->expiration,simTime() +ACTIVE_ROUTE_TIMEOUT);
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)
{
e->expiration=e->expiration+2.0;
}
cancelEvent(e->deleteMessage);
scheduleAt(e->expiration, e->deleteMessage);
return reply;
System Requirements
- omnet++ 3.3 p1
- Visual Studio .NET 2005/2008
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.