clique.cpp

传感器网络的可靠路由算法

#include "stdafx.h"
#include "Network.h"
#include "Clique.h"
#include "EventSim.h"
#include "Routing.h"


/* global variables */
extern NODE_TYPE nodeT[4000];
extern NETWORK_TYPE net;

extern int totaldirect, totalinter, totaldistant;


//insert a node(member) to a clique of a node(currenthop) 

void InsertNodeToClique(int member, int previoushop, int currenthop)
{
    double interlink;
	double intralink;
	interlink = linkquality(previoushop, member);
	intralink = linkquality(member, currenthop);
	assert(intralink>0);
	if (interlink<0)
		return;
    int i;
   for (i=nodeT[previoushop].NextClique.numItem-1; i>=0;i--)
	{
	    if (nodeT[previoushop].NextClique.intralink[i]<intralink)
		{ 		nodeT[previoushop].NextClique.Members[i+1]  = nodeT[previoushop].NextClique.Members[i];
	  	        nodeT[previoushop].NextClique.intralink[i+1]  = nodeT[previoushop].NextClique.intralink[i];
		    	nodeT[previoushop].NextClique.interlink[i+1]  = nodeT[previoushop].NextClique.interlink[i];

	    }
		else
			break;
   }
   nodeT[previoushop].NextClique.Members[i+1] = member;
   nodeT[previoushop].NextClique.intralink[i+1] = intralink;
   nodeT[previoushop].NextClique.interlink[i+1] = interlink;
   
  nodeT[previoushop].NextClique.numItem++;
  for (i=0;i<nodeT[previoushop].NextClique.numItem-1;i++)
	  assert(nodeT[previoushop].NextClique.intralink[i]>=nodeT[previoushop].NextClique.intralink[i+1]);
}



double linkquality2(int from, int to)
{
  if (linkquality(from,to)>=0)
	  return linkquality(from,to);
  else
	  return 0;

}


//Here this function tests in the view of from, whether n, nieghbor, is better than c, current 
//comparison interface as mentioned by the paper 

int IsBetterThanCurrent(int from, int n, int c)
{
	
	
    switch(net.ROUTING_TYPE){
	case MH:
		{
	
		  if ((nodeT[c].rt.routingItem[0].NextHop == n)&&(n!=c))
			  return 1;
		  else return 0;
		
		
		}
		
	case MH_A:
		{
		  if ((nodeT[c].rt.routingItem[0].NextHop == n)&&(n!=c))
			  return 1;
		  else return 0;
		
		}
	case GF:
		{
		    if (adistance(n,0)<adistance(c,0))
		         return 1;
			else return 0;
		}
	case GFX:
		{


            if (adistance(n,0)<adistance(c,0))
		         return 1;
			else return 0;
		
		}
	
    default: assert(false);
	}
}



//the implementation is one possiblity of many 

int distantsaving(int from, int to, int helper)
{
 double saving;
 double cost;
 
 saving = cost =0;

 if (unidirectional(from, helper)==1)
	  return 0;

 assert(unidirectional(to,helper)==0);


 saving = 1/(linkquality2(from, to)*linkquality2(to,from)) + net.LAMBDA/linkquality2(to,from);
 saving*= linkquality2(to,helper)*linkquality2(helper,to);

 cost = net.LAMBDA*(1+linkquality2(helper,to));
 cost+=  linkquality2(to,helper)*linkquality2(helper,to)*net.LAMBDA*(1/(linkquality2(helper,to)*linkquality2(to,helper))+1/linkquality2(to,helper));
 cost+=  linkquality2(to,helper)*linkquality2(helper,to)*net.LAMBDA*(1/(linkquality2(from,to)*linkquality2(to,from))+1/linkquality2(from,to));
 
 if (saving >cost)
	  return 1;
  else
	  return 0;

}


// yes better implementations may exist. 

int intermediatesaving(int from, int to, int helper)
{

 if (unidirectional(from, helper)==1)
	  return 0;

 assert(unidirectional(to,helper)==0);
 double saving;
 double cost;

 saving = cost = 0;

 saving = 1/(linkquality2(from, to)*linkquality2(to,from)) + net.LAMBDA/linkquality2(to,from) - (1/(linkquality2(helper, to)*linkquality2(to,helper)) + net.LAMBDA/linkquality2(to,helper)) ;
 saving*= linkquality2(to,helper)*linkquality2(helper,to);

 cost = net.LAMBDA*(1+linkquality2(helper,to));
 cost+=  linkquality2(to,helper)*linkquality2(helper,to)*net.LAMBDA*(1/(linkquality2(from,to)*linkquality2(to,from))+1/linkquality2(from,to));

  if (saving >cost)
	  return 1;
  else
	  return 0;


}


//discuss whether the probility of the packets received succussfully is above the threshold
int whetherreliable(int from,int to)
{
	double d;
	double p;
	d=adistance(from,to);
	if(d<=RANGE_THRESHOLD) 
		p=1-pow(double(d/RANGE_THRESHOLD),2*Value)/2;
	else 
		if ((d<=2*RANGE_THRESHOLD)&&(d>RANGE_THRESHOLD)) 
			p=pow(double((2*RANGE_THRESHOLD-d)/RANGE_THRESHOLD),2*Value)/2;
    if(p>=0.7) 
		return 1;
	else 
		return 0;
}

//BuildClique should try to build cliques based on the dest. 
//the building procedrure is based on the paper 

void BuildClique(int dest)
{
   
	
   int neighborindex;
   int index;
   int nexthop;
 
//this section of code puts all the neighbors into either the intermediate helper set or the distant helper set 

  for (index = 0; index < net.NUM_NODES; index++)
  
  {
      nexthop = nodeT[index].rt.routingItem[0].NextHop;
      if (index == nexthop)
		  continue;

	  for (neighborindex=0;neighborindex<nodeT[nexthop].neighbornum; neighborindex++)
		{
		   int tnode = nodeT[nexthop].neighbor[neighborindex];
  
		    if (unidirectional(tnode, nexthop)==true)
				  continue;

			if (tnode==index)
				continue;


			//for each neighbor, check if it is better, and whether it should act as  a distant helper or an intermediate helper 
		   if (IsBetterThanCurrent(index, tnode, nexthop)==1)
		   {  if ((distantsaving(index, nexthop, tnode)==1)&&(whetherreliable(index,tnode)==1))
			   //if (distantsaving(index, nexthop, tnode)==1)
			   {				  
				   nodeT[index].distantnum++;
		           nodeT[index].distanthelper[nodeT[index].distantnum-1] = tnode;
			   }
		   }
    	   else
		   {  if ((intermediatesaving(index, nexthop, tnode)==1)&&(whetherreliable(nexthop,tnode)==1))
			   //if (intermediatesaving(index, nexthop, tnode)==1)
              {				  
				   nodeT[index].internum++;
		           nodeT[index].interhelper[nodeT[index].internum-1] = tnode;
			  }
		   }
	  }
  
  
  
  }


  for (index = 0; index < net.NUM_NODES; index++)
 {
 
	 //for debugging 
 // printf("node %d hop %f has %d intermediate helper and %d distant helper\n", index, linkquality(index, nodeT[index].rt.routingItem[0].NextHop),nodeT[index].internum, nodeT[index].distantnum);
     // printf("%d   %d   %d   %d    %f\n", index, nodeT[index].distantnum, nodeT[index].internum, nodeT[index].distantnum+nodeT[index].internum,  linkquality2(index, nodeT[index].rt.routingItem[0].NextHop)*linkquality2(nodeT[index].rt.routingItem[0].NextHop, index));

  }
}








//This function builds the cost and delay for each hop using specific helpers 

//returns the next hop of the delivery


double sendsignalcost(int from, int to)
{
   double p,q;
   double u = net.LAMBDA;
   p = linkquality2(from, to);
   q = linkquality2(to,from);
   assert(p>0);
   assert(q>0);

  return u*(1/(p*q)+1/q);

}


double sendsignaldelay(int from, int to)
{
   double p,q;
   double l = net.LAMBDA;
   p = linkquality2(from, to);
   q = linkquality2(to,from);
   assert(p>0);
   assert(q>0);
   return (1/p-1)*(SEND_TIMEOUT+l)+l;
}



double senddatacost(int from, int to)
{   double p,q;
   double u = net.LAMBDA;
   p = linkquality2(from, to);
   q = linkquality2(to,from);
   assert(p>0);
   assert(q>0);

  return 1/(p*q)+u/q;


}


double senddatadelay(int from, int to)
{
   double p,q;
   p = linkquality2(from, to);
   q = linkquality2(to,from);
   assert(p>0);
   assert(q>0);
   return (1/p-1)*(SEND_TIMEOUT+1)+1;

}


//added with the hop wise transmission helper effect
//this function is the core part of the cluster dlivery algorithm 
//check with the paper to see its implementation 


int ClusterDelivery(int index, double *delay, double *cost)
{

	int succeed; 

	succeed = 0;
	double linkp, linkq;

	double temp1, temp2;
	

	int next;

	linkp = linkquality2(index, nodeT[index].rt.routingItem[0].NextHop);
	linkq = linkquality2(nodeT[index].rt.routingItem[0].NextHop, index);

  if ((nodeT[index].internum == 0)&&(nodeT[index].distantnum==0))
       {		
		   
               totaldirect++;
		        *cost = linkCost(index,nodeT[index].rt.routingItem[0].NextHop, 0);
	            *delay = linkDelay(index, nodeT[index].rt.routingItem[0].NextHop);
	             return nodeT[index].rt.routingItem[0].NextHop;
       }

	   next = nodeT[index].rt.routingItem[0].NextHop;
 
	   temp1 = linkCost(index,next,0);
	   temp2 = linkDelay(index, next);
	   //now send the data
	  do {
	    //try next node
          double previouscost, previousdelay;

		  previouscost =  *cost;
		  previousdelay = *delay;

	      if (RunEvent(linkquality2(index, next))==true)
		  { *delay = *delay+1;
		    *cost = *cost+1;			
		      totaldirect++;
			  return next;
		  }

	  //try distant ones
		  if (nodeT[index].distantnum >0)
		  {
		     int i;

			 if (next==0)
				 assert(false);

			 for (i=0;i<nodeT[index].distantnum;i++)
			 {	 
		         int helper =  nodeT[index].distanthelper[i];

			     if (RunEvent(linkquality2(index, helper))==true)
				{
	               if ((RunEvent(linkquality2(next, helper))==true)&&(RunEvent(linkquality2(helper,next))==true))
				    { *cost+=net.LAMBDA*2+sendsignalcost(helper,next)+ sendsignalcost(next,index);
				       *delay+=net.LAMBDA*2+sendsignaldelay(helper,next);
					   totaldistant++;//use an distant helper
				      return helper;
				   }
				   else
				   {
				      *cost+=net.LAMBDA+linkquality2(helper,next)*net.LAMBDA;
					  *delay+=net.LAMBDA*2;
				   }
				 }
				 else
				 {*delay+=net.LAMBDA*2;}
			 
			 }
		  
		  }

		  //try intermediate
		  if (nodeT[index].internum >0)
		  {
		   int i;

			for (i=0;i<nodeT[index].internum;i++)
			 {	 
		         int helper =  nodeT[index].interhelper[i];

			     if (RunEvent(linkquality2(index, helper))==true)
				{
	               if ((RunEvent(linkquality2(next, helper))==true)&&(RunEvent(linkquality2(helper,next))==true))
				    { *cost+=net.LAMBDA*2+senddatacost(helper,next)+ sendsignalcost(next,index);
				       *delay+=net.LAMBDA*2+senddatadelay(helper,next);
					   totalinter++;//use an inter helper
				      return next;
				   }
				   else
				   {
				      *cost+=net.LAMBDA+linkquality2(helper,next)*net.LAMBDA;
					  *delay+=net.LAMBDA*2;
				   }
				 }
                 			 else
				 {*delay+=net.LAMBDA*2;}			
			}