routing.cpp

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

#include "stdafx.h"
#include "network.h"
#include "routing.h"

//external variables 
extern NODE_TYPE nodeT[4000];
extern NETWORK_TYPE net;



void BuildRouting(){

    switch(net.ROUTING_TYPE){
	case MH:
		BuildMH(0);
		break;
	case MH_A:
		BuildMH_A(0); 
        break;
	case GF:
        BuildGF(0);
    break;
	case GFX:
		BuildGFX(0);
	    break;
    default: assert(false);
	}
}



double GetE2ECost(int nodeID, int Destination){

	assert(nodeID < net.NUM_NODES);
   	int index;

	for(index = 0 ; index < MAX_NUM_NEIGHBORS ; index++){
	  if(Destination == nodeT[nodeID].rt.routingItem[index].DenstinationID)
			  return nodeT[nodeID].rt.routingItem[index].Cost;
	}
    return MAXCOST;
}

//Set the routing item to destination as nexthop and with cost 

void SetNextHop(int nodeID, int Destination, int NextHop){

    assert(nodeID < net.NUM_NODES);
    
	int index;

    /* purge any higher cost items previously remained */
	for(index = 0 ; index < MAX_NUM_NEIGHBORS ; index++){
		
		if(Destination == nodeT[nodeID].rt.routingItem[index].DenstinationID) 
            assert(false);
	}
		



	/* if not, find an empty slot */
	if(index == MAX_NUM_NEIGHBORS)
	for(index = 0 ; index < MAX_NUM_NEIGHBORS ; index++){

	  if(INVALID_ID == nodeT[nodeID].rt.routingItem[index].DenstinationID){
            nodeT[nodeID].rt.routingItem[index].DenstinationID = Destination;
			nodeT[nodeID].rt.routingItem[index].NextHop = NextHop;
			nodeT[nodeID].rt.numItems++;
		  break;
	  }
     if(index == MAX_NUM_NEIGHBORS) { printf("Full!!!"); exit(-1);}
	}

    return;
}


double SetE2ECost(int nodeID, int Destination,double cost,int NextHop){

	assert(nodeID < net.NUM_NODES);
    
	int index;

    /* purge any higher cost items previously remained */
	for(index = 0 ; index < MAX_NUM_NEIGHBORS ; index++){
		
		if(Destination == nodeT[nodeID].rt.routingItem[index].DenstinationID) {

			if(cost < nodeT[nodeID].rt.routingItem[index].Cost){		
				nodeT[nodeID].rt.routingItem[index].DenstinationID = INVALID_ID;
				nodeT[nodeID].rt.numItems--;
				assert(nodeT[nodeID].rt.numItems >=0);
				if(net.ROUTING_TYPE == GF) assert(false);
			} else if(cost > nodeT[nodeID].rt.routingItem[index].Cost) {
				assert(false);
			}
		}		
	}

	for(index = 0 ; index < MAX_NUM_NEIGHBORS ; index++){
		/* if find a duplicate item do nothing*/
		if(Destination == nodeT[nodeID].rt.routingItem[index].DenstinationID &&
		   nodeT[nodeID].rt.routingItem[index].NextHop == NextHop && 
		   cost == nodeT[nodeID].rt.routingItem[index].Cost)
		   return cost;			
	}

	/* if not, find an empty slot */
	if(index == MAX_NUM_NEIGHBORS)
	for(index = 0 ; index < MAX_NUM_NEIGHBORS ; index++){

	  if(INVALID_ID == nodeT[nodeID].rt.routingItem[index].DenstinationID){
            nodeT[nodeID].rt.routingItem[index].DenstinationID = Destination;
			nodeT[nodeID].rt.routingItem[index].Cost = cost;
			nodeT[nodeID].rt.routingItem[index].NextHop = NextHop;
			nodeT[nodeID].rt.numItems++;
		  break;
	  }
     if(index == MAX_NUM_NEIGHBORS) { printf("Full!!!"); exit(-1);}
    }

    return MAXCOST;
}

/* identify next hop forwarding nodes. For single link routing algorithm, it should have
   only one nextHop. for clique-based algorithm, it could have multiple destinations
 */
 
 
int NextHop(int nodeID,int Destination){

	int index;

	assert(nodeID < net.NUM_NODES);
	assert(Destination < net.NUM_NODES);
	
	if(nodeID == Destination) return Destination;

	for(index = 0 ; index < nodeT[nodeID].rt.numItems ; index++){
	  if(Destination == nodeT[nodeID].rt.routingItem[index].DenstinationID)
				return nodeT[nodeID].rt.routingItem[index].NextHop;
			}  			
  
}


//now really used 
bool E2EPacket(int source,int dest,int time){
   
   int receiver;
   int nextID;

   assert(source < net.NUM_NODES);

   int currentNode = source;

   if(source == dest ) return true;
   
   /* receiver id can be node id or clique id */
   while((nextID = NextHop(currentNode,dest))!=INVALID_ID){       
	   
	   receiver = TransmitSimulation(currentNode,nextID);	   
	   
	   if(receiver != INVALID_ID){		 
        printf("transmission success form %d->%d at %d through %d",source,dest,currentNode,receiver);        
        currentNode = receiver;
		/* reach destination */
		if(currentNode == dest) return true;
		continue;
	   }else{
		   //printf("transmission failure form %d->%d at %d through %d",source,dest,currentNode,receiver);
		   return false;          
	   }
   }
   printf("Routing failure form %d->%d at %d",source,dest,currentNode);
   return false;
}