route.c

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

/*
****************************************************************************
*              宁波中科集成电路设计中心  版权所有 Copyright 2005
*						http:\\www.nbicc.com
*文件名：  route.h
*程序员：  蒋文丰
*主要内容  路由算法

*如有问题或BUG，请登录www.wsn.net.cn 提问或用邮件和作者联系
****************************************************************************
*/
#include "type.h"
#include "message.h"
#include "global.h"
#include "led.h"
#include "timer.h"
#include "os.h"
#include "route.h"
#include "dataqueue.h"
#include "app.h"

static void routeBroadcast(void);
static void UpdateTable(void);
static void tablemanage(uint8_t outdegree,bool acceptable,uint8_t sourceaddr,uint8_t hopcount,uint16_t broadno,OSMACMsgPtr receivemsg);
static uint8_t GetLocation(uint8_t addr);
static result_t ReceiveInLocal(uint8_t sourceaddr);
static result_t LocalAddrInReceive(OSMACMsgPtr receivemsg);
static void InParentBool(uint8_t addr,uint8_t location);
static void UpdateParentPool(void);
static uint8_t GetLocalOutDegree(void);
static uint8_t OutMapping(uint8_t i);

static uint8_t GetAnFreePlace(void);
static uint8_t GetAnPlace(void);
static uint8_t GetNoSym(void);
static uint8_t GetEqualMetric(void);
//static uint8_t GetLowMetric(void);

static void ChooseParent(void);
static uint8_t GetPerfect(void);
static bool HaveCircle(OSMACMsgPtr Msg,uint8_t nextAddr);
//static void FreshReceiveTime(void);

enum {NOSYMMETRICAL,SYMMETRICAL,CHANGEABLE};
uint8_t currentparent;
static uint8_t parentpool[MAXNEIGHBOR]; //下一跳节点备选缓冲池
static uint8_t EraserCount;//定期请空计数器
static uint8_t metric; //节点层号
static uint8_t freerecorder;//邻居表是否还有空间
static uint16_t broadseqno; //路由包号
static uint8_t  flag;//用于替换的时候从头或尾挑选，0为头1为尾
static OSMACMsg  routeMsg;
static OSMACMsgPtr routeMsgPtr;
static uint8_t DegreeTable[6];//注意要配合sink节点的梯度为1的不变得限制
/*************************************************************************
*功能描述：初始化路由
*参数说明：
*返回值：
*************************************************************************/
void RoutInit(void){
    uint8_t i;
	broadseqno = 0;          //路由广播包的序列号
    routeMsgPtr = &routeMsg; //获得路由广播包指针
    currentparent = INVALID_NODE_ID; 
	freerecorder = MAXNEIGHBOR;
	flag = 0;
	EraserCount = 0;
    if (OS_LOCAL_ADDRESS == SINKNODE) {
		metric = 1; //SINK始终为1,不能改动
	} else {
		metric = INVALID_NODE_ID; //其它节点初始为最大
	} 
	//路由表初始化
	for (i = 0; i < MAXNEIGHBOR; i++) {
		nbrTable[i].addr = INVALID_NODE_ID;
		nbrTable[i].state = CHANGEABLE;
		nbrTable[i].metric = INVALID_NODE_ID;
		nbrTable[i].broadseqno = 0;
		nbrTable[i].prebroadseqno = 0;
		nbrTable[i].sendfailtime = 0;
		///////
		nbrTable[i].outdegree = 0;
		parentpool[i] = INVALID_NODE_ID;
	}
	/////////出度映射表
	DegreeTable[0] = 20;
	DegreeTable[1] = 20;
	DegreeTable[2] = 10;
	DegreeTable[3] = 5;
	DegreeTable[4] = 3;
	DegreeTable[5] = 2;
}
/*************************************************************************
*功能描述：完成路由表的定期发送任务
*参数说明：
*返回值：
*************************************************************************/
void routeTimerTask(void) {
    EraserCount++;
	if(EraserCount >= 5) {
	EraserCount = 0;
	UpdateTable(); //清理路由表
	}
	UpdateParentPool();//修改缓冲池的数据
	OSPostTask(routeBroadcast); //发送广播包
} 

static void UpdateTable(void){
   uint8_t i;
   for (i = 0; i < MAXNEIGHBOR; i++) {
        if( nbrTable[i].broadseqno == nbrTable[i].prebroadseqno ){ //在指定的时间中没有收到该节点的任何路由包
		nbrTable[i].addr = INVALID_NODE_ID;
		if(nbrTable[i].state != CHANGEABLE ) freerecorder++;
		nbrTable[i].state = CHANGEABLE;
		nbrTable[i].metric = INVALID_NODE_ID;
		nbrTable[i].broadseqno = 0;
		nbrTable[i].prebroadseqno = 0;
		nbrTable[i].sendfailtime = 0;
		nbrTable[i].outdegree = 0;
		parentpool[i] = INVALID_NODE_ID;
		} else {
		nbrTable[i].prebroadseqno = nbrTable[i].broadseqno;
		}
   }
}

static void UpdateParentPool(void){
    uint8_t i;
	for(i = 0 ;i < MAXNEIGHBOR; i++) {
	if((nbrTable[i].state == SYMMETRICAL)&&(nbrTable[i].metric < metric )\
	&&(nbrTable[i].outdegree >= 1)) parentpool[i] = nbrTable[i].addr;
	else parentpool[i] = INVALID_NODE_ID;
	}
}
/*************************************************************************
*功能描述：路由包的建立和发送
*参数说明：
*返回值：
*************************************************************************/
static void routeBroadcast(void) {
	//发送广播包
	uint8_t length;
	uint8_t i;
    SHopMsgPtr sHopMsg;
	sHopMsg = (SHopMsgPtr )routeMsgPtr->data;
    
	sHopMsg->type = BROADCAST;
	sHopMsg->seq = broadseqno; //在发送完广播包以后需自加
    RoutePacket *broadPacket = (RoutePacket *) sHopMsg->data;
	if(GetFreeQueueLength() >= 1) broadPacket->QueueUseEnable = TRUE;
	else broadPacket->QueueUseEnable = FALSE;
	broadPacket->metric = metric;
	////
	if(OS_LOCAL_ADDRESS == SINKNODE ) broadPacket->outdegree = 255;
	else broadPacket->outdegree = GetLocalOutDegree();
    for (i = 0; i < MAXNEIGHBOR; i++) {
		broadPacket->neighbor[i] = nbrTable[i].addr;
	}
    
	length = sizeof(RoutePacket) + SHOP_HEADER_LEN;
    InBroadQueue(BROADCAST,length, routeMsgPtr);
} 

static uint8_t GetLocalOutDegree(void){
    uint8_t i;
	uint16_t tempoutdegree = 0;
	for(i = 0;i < MAXNEIGHBOR; i++) {
	if((nbrTable[i].addr != INVALID_NODE_ID)&&(nbrTable[i].state == SYMMETRICAL)\
    &&(nbrTable[i].metric <  metric)) tempoutdegree = tempoutdegree + OutMapping(i);
	}
	if(tempoutdegree > 255 ) return 255;
	else return (tempoutdegree&0xff);
}
static uint8_t OutMapping(uint8_t i){
    
    if(nbrTable[i].metric <= 6) return DegreeTable[nbrTable[i].metric - 1];
	else return 1;
}
/*************************************************************************
*功能描述：路由包的包号的递增
*参数说明：发送包指针
*返回值：
*************************************************************************/
void routeBroadcastDone(OSMACMsgPtr msg) {

    broadseqno++;
}

/*************************************************************************
*功能描述：接受到路由包，进行相关的处理
*参数说明：
*返回值：
*************************************************************************/
void routeReceiveBroadcast(OSMACMsgPtr receivemsg) {
	
	SHopMsgPtr sHopMsg;
	uint8_t sourceaddr;
    uint8_t hopcount;
	uint16_t broadno;
	bool   acceptable;
    uint8_t outdegree;
	
	sHopMsg = (SHopMsgPtr )receivemsg->data;
	broadno = sHopMsg->seq;
	RoutePacket *broadPacket = (RoutePacket *) sHopMsg->data;
   
	sourceaddr = receivemsg->fromAddr;
    hopcount = broadPacket->metric;
    acceptable = broadPacket->QueueUseEnable;
	outdegree = broadPacket->outdegree;
	
	LedGreenToggle();       //绿灯亮,表示接收到广播包
	
	tablemanage(outdegree,acceptable,sourceaddr,hopcount,broadno,receivemsg);
	
	if( OS_LOCAL_ADDRESS != SINKNODE ) {
	   ChooseParent();
	}
}

/*************************************************************************
*功能描述：路由表的修改（每收集到一个路由包都要修改路由表）
*参数说明：acceptable 标示路由包源是否有缓冲区
           sourceaddr 标示路由包源的地址
		   hopcount   标示路由包源的层号
		   broadno    标示该路由包号
		   receivemsg 标示接受到的包的指针
*返回值：
*************************************************************************/
static void tablemanage(uint8_t outdegree,bool acceptable,uint8_t sourceaddr,uint8_t hopcount,uint16_t broadno,OSMACMsgPtr receivemsg){
    uint8_t location;
	///metric变小最好暂时不要发送一个路由广播包，以防循环路由
	if(ReceiveInLocal(sourceaddr)){//发送路由包的节点在本节点的邻居表中
	location = GetLocation(sourceaddr);//定位相关路由记录表项
	       if(LocalAddrInReceive(receivemsg)){ //本节点在路由包的源节点的邻居表中
		      nbrTable[location].state = SYMMETRICAL;
				  if (hopcount < ( metric - 1 ) ) {
				    metric = hopcount + 1; 
					if(acceptable&&(outdegree >= 1 )) InParentBool(nbrTable[location].addr,location);
				  }
	       }else {
		   nbrTable[location].state = NOSYMMETRICAL;
		   }
    nbrTable[location].metric = hopcount;
	nbrTable[location].broadseqno = broadno;
	nbrTable[location].outdegree = outdegree;	  
	} else {
	    if(freerecorder >= 1 ) {//路由表中还有空间
	      location = GetAnFreePlace();
		  nbrTable[location].addr = sourceaddr;
		  if(LocalAddrInReceive(receivemsg)){
		         nbrTable[location].state = SYMMETRICAL;
		         if (hopcount < ( metric - 1 ) ) {
				    metric = hopcount + 1;
                    if(acceptable&&(outdegree >= 1 )) InParentBool(nbrTable[location].addr,location); 
				  }
		  } else {
		    nbrTable[location].state = NOSYMMETRICAL;
		  }
		  nbrTable[location].metric = hopcount;
		  nbrTable[location].broadseqno = broadno;
		  nbrTable[location].prebroadseqno = nbrTable[location].broadseqno;
		  nbrTable[location].sendfailtime = 0;
		  nbrTable[location].outdegree = outdegree;
		  freerecorder--;
		 //这里可以加入发送路由包的任务，加快路由标的更新速度
	    } else { //路由表满，启动替换策略
		  location = GetAnPlace();
		  if(location < MAXNEIGHBOR ) {
			  nbrTable[location].addr = sourceaddr;
			  parentpool[location] = INVALID_NODE_ID;//替换先消去
			  if(LocalAddrInReceive(receivemsg)){
					 nbrTable[location].state = SYMMETRICAL;
					 if (hopcount < ( metric - 1 ) ) {
					    metric = hopcount + 1;
                        if(acceptable&&(outdegree >= 1 )) InParentBool(nbrTable[location].addr,location);
					  }
			  } else {
				nbrTable[location].state = NOSYMMETRICAL;
			  }
			  nbrTable[location].metric = hopcount;
			  nbrTable[location].broadseqno = broadno;
			  nbrTable[location].prebroadseqno = nbrTable[location].broadseqno;
		      nbrTable[location].sendfailtime = 0;
			  nbrTable[location].outdegree = outdegree;
			}
	    } 
	}
}

/*************************************************************************