clique.cpp

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

		  
		  
		  }
	  
	  
	  if ((nodeT[index].internum>0)||(nodeT[index].distantnum>0))
	        *delay = previousdelay+SEND_TIMEOUT+1;
	  
		  
		  //end while
	    }
	  while (succeed == 0);

 }


	  




//this function is called by buildclustercost, below

void BuildNodeCost(int index, int dest)
{
   


   double currentdelay =0;
   double currentcost = 0;


   double accumulatedelay = 0;
   double accumulatecost = 0;

   int currentnode;
   
   currentnode = index;

  
      if (index==0)
	  {		 nodeT[index].rt.routingItem[0].CliqueCost = nodeT[index].rt.routingItem[0].CliqueDelay = 0;
	             return;
	  }
     
	  
    
     while (currentnode!=dest)
	 {
	     currentdelay = currentcost = 0;
		 currentnode = ClusterDelivery(currentnode, &currentdelay, &currentcost);
	     accumulatedelay+=currentdelay;
		 accumulatecost+=currentcost;

	 
	 }
 
	 nodeT[index].rt.routingItem[0].CliqueCost = accumulatecost;
     nodeT[index].rt.routingItem[0].CliqueDelay = accumulatedelay;

}
	

//build the cost of clusters 
void BuildClusterCost(int dest)
{
  int index;
  for (index = 0; index < net.NUM_NODES; index++)
	  BuildNodeCost(index, dest);


}








//for the use of cliques 

void SortNode(int index, int dest)
{
   int i,j;

   for (i=0;i<nodeT[index].internum; i++)
    for (j=0;j<nodeT[index].internum;j++) 
	{
	    double p1,q1,p2, q2;
        int next,helper1, helper2;


		if (i==j)
			continue;
		next = nodeT[index].rt.routingItem[0].NextHop;
		helper1 = nodeT[index].interhelper[i];
        helper2 = nodeT[index].interhelper[j];

		p1 = linkquality(next,helper1);
		q1 = linkquality(helper1,next);
        p2 = linkquality(next,helper2);
		q2 = linkquality(helper2,next);
		if (p1*q1<p2*q2)
		{nodeT[index].interhelper[i] = helper2;
	      nodeT[index].interhelper[j] = helper1;
		}
	}

   for (i=0;i<nodeT[index].distantnum; i++)
    for (j=0;j<nodeT[index].distantnum;j++) 
	{
		double d1,d2,d3;
		int next,helper1, helper2;
		double temp1, temp2;
        double p1,q1, p2,q2;
		if (i==j)
			continue;
	
		assert((net.ROUTING_TYPE == GFX)||(net.ROUTING_TYPE == GF));
		next = nodeT[index].rt.routingItem[0].NextHop;
		helper1 = nodeT[index].distanthelper[i];
        helper2 = nodeT[index].distanthelper[j];

		d1 = adistance(helper1, dest);
		d2 = adistance(helper2, dest);
		d3 = adistance(index, dest);
        p1 = linkquality2(index, helper1);
        q1 = linkquality2(helper1, index);
        p2 = linkquality2(index, helper2);
        q2 = linkquality2(helper2, index);
        
		temp1 = (d3-d1)*p1;
		temp2 = (d3-d2)*p2;
		
		assert(d3>d1);
		assert(d3>d2);
		
		if (net.ROUTING_TYPE == GFX)
		if (temp1<temp2)
		{nodeT[index].distanthelper[i] = helper2;
	      nodeT[index].distanthelper[j] = helper1;
		}

		if (net.ROUTING_TYPE == GF)
		{
		   if (d1>d2)
           {nodeT[index].distanthelper[i] = helper2;
	         nodeT[index].distanthelper[j] = helper1;
		   }
		}
	  
	
	}

}



void SortClique(int dest)
{
   
 int index;
  for (index = 0; index < net.NUM_NODES; index++)
	  SortNode(index, dest);

}















/////////////////////////////////////////////////////////////////////////////////////////////////////////////


//This function should calculate the cost of delivering the packet over one hop

void CliqueSendCost(int current, int dest, double *cost, double *delay)
{
    bool LastHop;
	int nexthop;
	
	nexthop = NextHop(current, dest);
    
	
	if (current==dest)
	   {*cost = 0;
	     *delay = 0;
		 return;
	   }  
    if (nexthop == dest)
		LastHop = true;
	else
		LastHop = false;

	 
	int members[100];
	int numofmember;
	
	for (int i=0;i<nodeT[current].NextClique.numItem;i++)
		members[i]= nodeT[current].NextClique.Members[i];
	
	numofmember= nodeT[current].NextClique.numItem;

	if (numofmember==0)
	{  *cost = linkCost(current,nexthop,dest);
	    *delay = linkDelay(current,nexthop);
		return;
	}

	//Run the simulator

	double sendcost, sendtime;

	CostCliqueSendNative(current, nexthop, numofmember, members, &sendcost, &sendtime);
	
   *cost = sendcost;
   *delay = sendtime;
   return;

}



void CliqueSendCostOptimized(int current, int dest, double *cost, double *delay)
{

  bool LastHop;
  int nexthop;

	
	nexthop = NextHop(current, dest);
    
	
	if (current==dest)
		 {*cost = 0;
	       *delay = 0;
		   return;
	     }  
    if (nexthop == dest)
		LastHop = true;
	else
		LastHop = false;

	 
	int members[100];
	int numofmember;
	int numofbetternode;
	int betternodes[100];
	numofbetternode = 0;
	int i;

	for (i=0;i<nodeT[current].NextClique.numItem;i++)
		members[i]= nodeT[current].NextClique.Members[i];
	
	numofmember= nodeT[current].NextClique.numItem;

	if (numofmember==0)
		{  *cost = linkCost(current,nexthop,dest);
	        *delay = linkDelay(current,nexthop);
			return;
	    }


	//Now find out those even better nodes and place them in betternodes 

	for (i=0;i<numofmember; i++)
	{if (adistance(members[i],dest)<adistance(nexthop, dest))
		{
		  betternodes[numofbetternode] = members[i];
      	  numofbetternode++;
		  for (int j=i;j<numofmember-1;j++)
			  members[j] = members[j+1];
		  numofmember--;
		  i--;
		}
	}
	//Run the simulator

	double sendcost, sendtime;

	CostCliqueSendOptimized(current, nexthop, numofmember, members, numofbetternode, betternodes, &sendcost, &sendtime);
	
	*cost = sendcost;
	*delay = sendtime;

	return;

}





void BuildCliqueToDestCost(int dest)
{
 
  int index;
 
  for (index = 0; index < net.NUM_NODES; index++)
   {
     int currentnode;
	 double accumulatecost;
	 double accumulatedelay;

	 accumulatecost = 0;
	 accumulatedelay = 0;
	 currentnode = index;
     
 while (currentnode!=dest)
        {accumulatecost+= nodeT[currentnode].nexthopcost;
          accumulatedelay+= nodeT[currentnode].nexthopdelay;
          currentnode = nodeT[currentnode].rt.routingItem[0].NextHop;
        } 
          	      
        nodeT[index].destcost  = accumulatecost;
		nodeT[index].destdelay = accumulatedelay;
    }
}
  
void BuildCliqueToDestCostOptimized(int dest)
{
 
  int index;

  for (index = 0; index < net.NUM_NODES; index++)
   {
     int currentnode;
	 double accumulatecost;
	 double accumulatedelay;

	 accumulatecost = 0;
	 accumulatedelay = 0;
	 currentnode = index;
     
 while (currentnode!=dest)
        {accumulatecost+= nodeT[currentnode].nexthopcost;
          accumulatedelay+= nodeT[currentnode].nexthopdelay;
          if (nodeT[currentnode].optimizednexthop ==-1)
		  currentnode = nodeT[currentnode].rt.routingItem[0].NextHop;
		  else
		  currentnode = nodeT[currentnode].optimizednexthop ;

        } 
          	      
        nodeT[index].destcost  = accumulatecost;
		nodeT[index].destdelay = accumulatedelay;
    }
}

void BuildCliqueCost(int dest)
{

	for (int i=0;i<net.NUM_NODES;i++)
	{
	 if (i==dest)
	   {nodeT[i].nexthopcost = nodeT[i].nexthopdelay= 0;
	     continue;}
	 
	   CliqueSendCost(i, dest, &nodeT[i].nexthopcost, &nodeT[i].nexthopdelay);

	}

BuildCliqueToDestCost(dest);
}

void BuildCliqueCost2(int dest)
{
    for (int i=0;i<net.NUM_NODES;i++)
	{
	   nodeT[i].optimizednexthop= -1;
	
	}
	for (int i=0;i<net.NUM_NODES;i++)
	{
	 if (i==dest)
	   {nodeT[i].nexthopcost = nodeT[i].nexthopdelay= 0;
	     continue;}
	 
	   CliqueSendCostOptimized(i, dest, &nodeT[i].nexthopcost, &nodeT[i].nexthopdelay);

	}

BuildCliqueToDestCostOptimized(dest);


}

void DisplayResults(int dest)  
  {
     
	for (int i=0;i<net.NUM_NODES;i++)
		printf("Node %d has cost %f delay %f 	VS cost %f delay %f\n", i,nodeT[i].rt.routingItem[0].Cost, nodeT[i].rt.routingItem[0].Delay, nodeT[i].destcost, nodeT[i].destdelay);
 }

void DisplayCliqueInfo()
{

   for (int i=0;i<net.NUM_NODES;i++)
   {
	   printf("node %d has clique member of %d\n", i, nodeT[i].NextClique.numItem);
      
   }


}