route.c

一个WSN的树状路由,对于那些学WSN路由方面的朋友应该有说帮助.

*功能描述：找到相关的邻居表中的纪录项，不过该数据项一定要在表项中
*参数说明：需要寻找的节点号
*返回值：  节点在表项中的位置
*************************************************************************/
static uint8_t GetLocation(uint8_t addr){
    uint8_t i;
	for(i = 0 ;i < MAXNEIGHBOR; i++) {
	if( nbrTable[i].addr == addr ) return i;
	}
}

/*************************************************************************
*功能描述: 检查路由包的源节点是否在本地的邻居表中
*参数说明：路由包的源节点号
*返回值：  TRUE OR FALSE
*************************************************************************/
static result_t ReceiveInLocal(uint8_t sourceaddr){
    uint8_t i;
	for(i = 0 ;i < MAXNEIGHBOR; i++) {
	if( nbrTable[i].addr == sourceaddr ) return 1;
	}
	return 0;
}

/*************************************************************************
*功能描述: 检查路由包的源节点的邻居表中是否包含本地节点号
*参数说明：接受到的数据包的指针
*返回值：  TRUE OR FALSE
*************************************************************************/
static result_t LocalAddrInReceive(OSMACMsgPtr receivemsg){
    uint8_t i;
	SHopMsgPtr sHopMsg;
	sHopMsg = (SHopMsgPtr )receivemsg->data;
	RoutePacket *broadPacket = (RoutePacket *) sHopMsg->data;
	for(i = 0; i < MAXNEIGHBOR; i++) {
	if( broadPacket->neighbor[i] == OS_LOCAL_ADDRESS ) return 1;
	}
	return 0;
    
}

static void InParentBool(uint8_t addr,uint8_t location){
    //入下一跳备选节点缓冲池
    parentpool[location] = addr;
}
////////////////////////////////////////////////////////////////
//这一部分用来获得一个放置新收到的节点信息的表项位置
///////////////////////////////////////////////////////////////
/*************************************************************************
*功能描述: 邻居表还有空间，获得一个空间
*参数说明：
*返回值：  空闲空间的位置
*************************************************************************/
static result_t GetAnFreePlace(void){
    uint8_t i;
	for(i = 0 ;i < MAXNEIGHBOR; i++) {
	if( nbrTable[i].addr == INVALID_NODE_ID ) return i;
	}
}

/*************************************************************************
*功能描述: 邻居表满，找到一个替换的空间
*参数说明：接受到的数据包的指针
*返回值：  TRUE OR FALSE
*************************************************************************/
static uint8_t GetAnPlace(void){
    uint8_t replace;
	replace = GetNoSym();
	if(replace > MAXNEIGHBOR) {
		replace = GetEqualMetric();
	}
	return replace;
}

/*************************************************************************
*功能描述: 找链路状况非对称的替换表项
*参数说明：
*返回值：  如果找到就返回位置，否则返回一个无效的值
*************************************************************************/
static uint8_t GetNoSym(void){
    uint8_t i;
	if(flag == 0){
	flag = 1;
		for(i = 0 ;i < MAXNEIGHBOR; i++) {  
		  if(nbrTable[i].state == NOSYMMETRICAL) return i;
		} 
	} else {
	flag = 0;
		for(i = MAXNEIGHBOR  ;i > 0; i--) {  //避免溢出
			  if(nbrTable[i - 1].state == NOSYMMETRICAL) return (i - 1);
			} 
	}
	return (MAXNEIGHBOR + 10);
}

/*************************************************************************
*功能描述: 找到层数==本地节点的替换表项
*参数说明：
*返回值：  如果找到就返回位置，否则返回一个无效的值
*************************************************************************/
static uint8_t GetEqualMetric(void){
    uint8_t i;
	for(i = 0 ;i < MAXNEIGHBOR; i++) {  
		  if(nbrTable[i].metric == metric) {
		  return i;
		  } 
	} 
	return (MAXNEIGHBOR + 10);
}

/*************************************************************************
*功能描述: 找到层数<本地节点的替换表项
*参数说明：
*返回值：  如果找到就返回位置，否则返回一个无效的值
*************************************************************************/
/*
static uint8_t GetLowMetric(void){
   uint8_t i;
   for(i = 0 ;i < MAXNEIGHBOR; i++) {
    if(nbrTable[i].metric < metric ){
	   if(nbrTable[i].sendfailtime == 0) return i; 
	}
   }
   return (MAXNEIGHBOR + 10);
}
*/
/////////////////////////////////////////////////////////////////////////
//选择下一跳的节点号
////////////////////////////////////////////////////////////////////////
/*************************************************************************
*功能描述: 找到下一跳的节点号
*参数说明：
*返回值：  
*************************************************************************/
static void ChooseParent(void){
    uint8_t i;
	uint8_t location;
	location = GetPerfect();//选择最好的下一跳，即有对称性，层数最低的那一项
	if( location < MAXNEIGHBOR ) {
	i = location + 1;
	  for( ; i < MAXNEIGHBOR ;i++){
	  //进一步寻找最优的点
	  if((nbrTable[i].state == SYMMETRICAL)&&(nbrTable[i].metric <= nbrTable[location].metric )) {
	       if((nbrTable[i].metric < nbrTable[location].metric)&&(nbrTable[i].outdegree >= 1)) location = i;
		   else if((nbrTable[i].metric == nbrTable[location].metric)\
		   &&(nbrTable[i].outdegree > nbrTable[location].outdegree))  location = i;
	     }
	  }
	} 
	
	if(location < MAXNEIGHBOR ) {
	currentparent = nbrTable[location].addr;
	} else { //找不到合适的下一跳节点
	currentparent = INVALID_NODE_ID;
	}
	
	if( OS_LOCAL_ADDRESS != SINKNODE ) {
	    if(currentparent == INVALID_NODE_ID ){ //层数下降要加速通报
			if(metric < INVALID_NODE_ID) metric++;
			else metric = INVALID_NODE_ID;
			OSPostTask(routeBroadcast);  
		}
	}
}

/*************************************************************************
*功能描述: 找到一个比较优的下一跳节点号
*参数说明：
*返回值：  如果找到就返回位置，否则返回一个无效的值
*************************************************************************/
static uint8_t GetPerfect(void){
    uint8_t i;
	for(i = 0 ;i < MAXNEIGHBOR; i++) {
	//找到一个合适的最优解
	if((nbrTable[i].state == SYMMETRICAL)&&(nbrTable[i].metric < metric )\
	&&(nbrTable[i].outdegree >=1)) return i;
	}
    return (MAXNEIGHBOR)+10;//找不到合适的最优点
}


///////////////////////////////////////////////////////
/*************************************************************************
*功能描述: 数据包发送失败对所选下一跳节点的重新评估
*参数说明：发送失败的数据包选择的下一跳节点号
*返回值：  
*************************************************************************/
void RouteChangeP(uint8_t addr){
    uint8_t i;
    for(i = 0 ;i < MAXNEIGHBOR; i++) {
		if(nbrTable[i].addr == addr) {
		nbrTable[i].sendfailtime ++;
			if(nbrTable[i].sendfailtime >= 3) {
			nbrTable[i].state = NOSYMMETRICAL;
			nbrTable[i].sendfailtime = 0;
			parentpool[i] = INVALID_NODE_ID;//去掉缓冲池中的该项
			ChooseParent();//重新选择下一跳节点
			 }
		}
	}
}

/*************************************************************************
*功能描述: 对所有邻居的接受次数的重新评估
*参数说明：
*返回值：  
*************************************************************************/
/*
static void FreshReceiveTime(void){
    uint8_t i;
    for(i = 0 ;i < MAXNEIGHBOR; i++) {
	nbrTable[i].receivetime = 0;
	}
}
*/
/*************************************************************************
*功能描述: 接受到数据包对相关节点的重新评估
*参数说明：接受到的数据包的节点号
*返回值：  
*************************************************************************/
/*
void RouteChangeH(uint8_t addr){
    uint8_t i;
	for(i = 0 ;i < MAXNEIGHBOR; i++) {
		if(nbrTable[i].addr == addr) {
		nbrTable[i].receivetime ++;
		if(nbrTable[i].receivetime >= 4 ) FreshReceiveTime();
		nbrTable[i].receivetime = 1;
		}
	}
}
*/
/*************************************************************************
*功能描述: 数据包发送成功对所选下一跳节点的重新评估
*参数说明：发送成功的数据包选择的下一跳节点号
*返回值：  
*************************************************************************/
void RouteChangeV(uint8_t addr){
    uint8_t i;
	for(i = 0 ;i < MAXNEIGHBOR; i++) {
		if(nbrTable[i].addr == addr) {
		nbrTable[i].sendfailtime = 0;
		}
	}
}

///////////////////////////////////////////////////////////////////////
//选择一个比较好的路由，尽量避免循环路由
/*************************************************************************
*功能描述: 为待发送的数据包选择一个不会造成循环的下一跳节点
*参数说明: 等待发送的数据包
*返回值：  选择的下一跳节点号 
*************************************************************************/
uint8_t CheckRoute(OSMACMsgPtr Msg){
    uint8_t i;
	if(currentparent == INVALID_NODE_ID ) return (INVALID_NODE_ID);
	if(HaveCircle(Msg,currentparent)) {  //优先选择currentparent
	    for(i = 0 ;i < MAXNEIGHBOR; i++) {
			if(parentpool[i] != INVALID_NODE_ID) {
			    if(!(HaveCircle(Msg,parentpool[i]))) return (parentpool[i]);
			}
		}
	} else {
	return (currentparent);
	}
	return (INVALID_NODE_ID);//没有好的路由选项，需要讨论在这种情况下是否应该使用默认的currentparent
}

/*************************************************************************
*功能描述: 检查选择的节点是否在待发送的数据包的路由链路中
*参数说明：OSMACMsgPtr Msg 待发送的数据包
           uint8_t nextAddr 选择的下一跳节点号
*返回值：  TRUE/FALSE
*************************************************************************/
static bool HaveCircle(OSMACMsgPtr Msg,uint8_t nextAddr){
    uint8_t i;
    SHopMsgPtr sHopMsg;
	SensorMsg *sensordata;
	
	sHopMsg = (SHopMsgPtr )Msg->data;
	sensordata = (SensorMsg *) (sHopMsg->data);
	
	for(i = 0 ;i < MAXPASS; i++) {
	    if (sensordata->passnode[i] != 0) {
	    if(sensordata->passnode[i] == nextAddr) return 1;
		} else {
		break;
		}
	}
	return 0;
}