aodv.cc.bak

Ad hoc网络的典型的距离矢量路由算法Aodv

 }

if (ih->daddr() == (nsaddr_t) IP_BROADCAST) {
 // If it is a broadcast packet
   assert(rt == 0);
   /*
    *  Jitter the sending of broadcast packets by 10ms
    */
   Scheduler::instance().schedule(target_, p,
      				   0.01 * Random::uniform());
 }
 else { // Not a broadcast packet 
   if(delay > 0.0) {
     Scheduler::instance().schedule(target_, p, delay);
   }
   else {
   // Not a broadcast packet, no delay, send immediately
     Scheduler::instance().schedule(target_, p, 0.);
   }
 }

}


void
AODV::sendRequest(nsaddr_t dst) {
// Allocate a RREQ packet 
Packet *p = Packet::alloc();
struct hdr_cmn *ch = HDR_CMN(p);
struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_request *rq = HDR_AODV_REQUEST(p);
aodv_rt_entry *rt = rtable.rt_lookup(dst);

 assert(rt);

 /*
  *  Rate limit sending of Route Requests. We are very conservative
  *  about sending out route requests. 
  */

 if (rt->rt_flags == RTF_UP) {
   assert(rt->rt_hops != INFINITY2);
   Packet::free((Packet *)p);
   return;
 }

 if (rt->rt_req_timeout > CURRENT_TIME) {
   Packet::free((Packet *)p);
   return;
 }

 // rt_req_cnt is the no. of times we did network-wide broadcast
 // RREQ_RETRIES is the maximum number we will allow before 
 // going to a long timeout.

 if (rt->rt_req_cnt > RREQ_RETRIES) {
   rt->rt_req_timeout = CURRENT_TIME + MAX_RREQ_TIMEOUT;
   rt->rt_req_cnt = 0;
 Packet *buf_pkt;
   while ((buf_pkt = rqueue.deque(rt->rt_dst))) {
       drop(buf_pkt, DROP_RTR_NO_ROUTE);
   }
   Packet::free((Packet *)p);
   return;
 }

#ifdef DEBUG
   fprintf(stderr, "(%2d) - %2d sending Route Request, dst: %d\n",
                    ++route_request, index, rt->rt_dst);
#endif // DEBUG

 // Determine the TTL to be used this time. 
 // Dynamic TTL evaluation - SRD

 rt->rt_req_last_ttl = max(rt->rt_req_last_ttl,rt->rt_last_hop_count);

 if (0 == rt->rt_req_last_ttl) {
 // first time query broadcast
   ih->ttl_ = TTL_START;
 }
 else {
 // Expanding ring search.
   if (rt->rt_req_last_ttl < TTL_THRESHOLD)
     ih->ttl_ = rt->rt_req_last_ttl + TTL_INCREMENT;
   else {
   // network-wide broadcast
     ih->ttl_ = NETWORK_DIAMETER;
     rt->rt_req_cnt += 1;
   }
 }

 // remember the TTL used  for the next time
 rt->rt_req_last_ttl = ih->ttl_;

 // PerHopTime is the roundtrip time per hop for route requests.
 // The factor 2.0 is just to be safe .. SRD 5/22/99
 // Also note that we are making timeouts to be larger if we have 
 // done network wide broadcast before. 

 rt->rt_req_timeout = 2.0 * (double) ih->ttl_ * PerHopTime(rt); 
 if (rt->rt_req_cnt > 0)
   rt->rt_req_timeout *= rt->rt_req_cnt;
 rt->rt_req_timeout += CURRENT_TIME;

 // Don't let the timeout to be too large, however .. SRD 6/8/99
 if (rt->rt_req_timeout > CURRENT_TIME + MAX_RREQ_TIMEOUT)
   rt->rt_req_timeout = CURRENT_TIME + MAX_RREQ_TIMEOUT;
 rt->rt_expire = 0;

#ifdef DEBUG
 fprintf(stderr, "(%2d) - %2d sending Route Request, dst: %d, tout %f ms\n",
	         ++route_request, 
		 index, rt->rt_dst, 
		 rt->rt_req_timeout - CURRENT_TIME);
#endif	// DEBUG
	

 // Fill out the RREQ packet 
 // ch->uid() = 0;
 ch->ptype() = PT_AODV;
 ch->size() = IP_HDR_LEN + rq->size();
 ch->iface() = -2;
 ch->error() = 0;
 ch->addr_type() = NS_AF_NONE;
 ch->prev_hop_ = index;          // AODV hack

 ih->saddr() = index;
 ih->daddr() = IP_BROADCAST;
 ih->sport() = RT_PORT;
 ih->dport() = RT_PORT;

    

 // Fill up some more fields. 
 rq->rq_type = AODVTYPE_RREQ;
 rq->rq_hop_count = 1;
 rq->rq_bcast_id = bid++;
 rq->rq_dst = dst;
 rq->rq_dst_seqno = (rt ? rt->rt_seqno : 0);
 rq->rq_src = index;
 seqno += 2;
 assert ((seqno%2) == 0);
 rq->rq_src_seqno = seqno;
 rq->rq_timestamp = CURRENT_TIME;

 Scheduler::instance().schedule(target_, p, 0.);

}

void
AODV::sendReply(nsaddr_t ipdst, u_int32_t hop_count, nsaddr_t rpdst,
                u_int32_t rpseq, u_int32_t lifetime, double timestamp) {
Packet *p = Packet::alloc();
struct hdr_cmn *ch = HDR_CMN(p);
struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p);
aodv_rt_entry *rt = rtable.rt_lookup(ipdst);

#ifdef DEBUG
fprintf(stderr, "sending Reply from %d at %.2f\n", index, Scheduler::instance().clock());
#endif // DEBUG
 assert(rt);

 rp->rp_type = AODVTYPE_RREP;
 //rp->rp_flags = 0x00;
 rp->rp_hop_count = hop_count;
 rp->rp_dst = rpdst;
 rp->rp_dst_seqno = rpseq;
 rp->rp_src = index;
 rp->rp_lifetime = lifetime;
 rp->rp_timestamp = timestamp;

 // ch->uid() = 0;
 ch->ptype() = PT_AODV;
 ch->size() = IP_HDR_LEN + rp->size();
 ch->iface() = -2;
 ch->error() = 0;
 ch->addr_type() = NS_AF_INET;
 ch->next_hop_ = rt->rt_nexthop;
 ch->prev_hop_ = index;          // AODV hack
 ch->direction() = hdr_cmn::DOWN;

 ih->saddr() = index;
 ih->daddr() = ipdst;
 ih->sport() = RT_PORT;
 ih->dport() = RT_PORT;
 ih->ttl_ = NETWORK_DIAMETER;

 Scheduler::instance().schedule(target_, p, 0.);

}

void
AODV::sendError(Packet *p, bool jitter) {
struct hdr_cmn *ch = HDR_CMN(p);
struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_error *re = HDR_AODV_ERROR(p);
    
#ifdef ERROR
fprintf(stderr, "sending Error from %d at %.2f\n", index, Scheduler::instance().clock());
#endif // DEBUG

 re->re_type = AODVTYPE_RERR;
 //re->reserved[0] = 0x00; re->reserved[1] = 0x00;
 // DestCount and list of unreachable destinations are already filled

 // ch->uid() = 0;
 ch->ptype() = PT_AODV;
 ch->size() = IP_HDR_LEN + re->size();
 ch->iface() = -2;
 ch->error() = 0;
 ch->addr_type() = NS_AF_NONE;
 ch->next_hop_ = 0;
 ch->prev_hop_ = index;          // AODV hack
 ch->direction() = hdr_cmn::DOWN;       //important: change the packet's direction

 ih->saddr() = index;
 ih->daddr() = IP_BROADCAST;
 ih->sport() = RT_PORT;
 ih->dport() = RT_PORT;
 ih->ttl_ = 1;

 // Do we need any jitter? Yes
 if (jitter)
 	Scheduler::instance().schedule(target_, p, 0.01*Random::uniform());
 else
 	Scheduler::instance().schedule(target_, p, 0.0);

}


/*
   Neighbor Management Functions
*/

#include <math.h> 
#include <mobilenode.h>
#define   PI 3.1415926535897   
#define   RADIAN(a)  (a*PI/180.0)              //根据角度获得弧度   
#define   ANGLE(r)   (180.0*r/PI)              //根据弧度获得角度  

double
AODV::ComptAngle(double x0,double y0,double x,double y)
{
double  cx,cy; 
double  dAngle;                    
/*MobileNode*	next_; ?inline MobileNode* nextnode() { return link_.le_next; }?    
下一个邻居节点的坐标获得   
struct neighbor_list_node {
	int nodeid;
	neighbor_list_node* next;
}; */

cx=x-x0;   
cy=y-y0;                                  //节点本身坐标x,y 

if(fabs(cx)>0)                            //cx不等于0
{
dAngle = ANGLE(atan(cy/cx));              //(90,-90)之间 
if(dAngle>0)
{
if(cx<0)  dAngle += 180.0;
}
else if(dAngle<0)
{
if(cy>0)  dAngle = 180+dAngle;
else dAngle = 360+dAngle;
}
else
{
if(cx<0) dAngle = 180;
}
}
else
{
if(cy>0)dAngle = 90.0;
else dAngle = 270.0;
}
return dAngle;
}

/*创建MobileNode的派生类CMobileNode ? 或者用聚合类?
static class CMobileNode : public MobileNode
{public 
CMobileNode()；
void setValue();
private:	
}*/


void
AODV::sendHello() {                                                  
Packet *p = Packet::alloc();
struct hdr_cmn *ch = HDR_CMN(p);
struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_reply *rh = HDR_AODV_REPLY(p);
struct hdr_aodv_topocontrol *th = HDR_AODV_TOPOCONTROL(p);                     //new

#ifdef DEBUG
fprintf(stderr, "sending Hello from %d at %.2f\n", index, Scheduler::instance().clock());
#endif // DEBUG

 MobileNode *mnode = new MobileNode;                                      //new creat移动节点 对象指针(非移动节点speed=0)
/* AODV_Neighbor *nb;
 
 x = mnode->X_;
 y = mnode->Y_;
 x0 = nb->nb_current_x；
 y0 = nb->nb_current_y;
 Angle = ComptAngle(nb->nb_current_x,nb->nb_current_y,th->current_pos_x,th->current_pos_y);  //本节点坐标x,y 调用函数comptAngle，得到dAngle 
 */  

 rh->rp_type = AODVTYPE_HELLO;
 //rh->rp_flags = 0x00;
 rh->rp_hop_count = 1;
 rh->rp_dst = index;
 rh->rp_dst_seqno = seqno;
 rh->rp_lifetime = (1 + ALLOWED_HELLO_LOSS) * HELLO_INTERVAL;


 // ch->uid() = 0;
 ch->ptype() = PT_AODV;
 ch->size() = IP_HDR_LEN + rh->size();
 ch->iface() = -2;
 ch->error() = 0;
 ch->addr_type() = NS_AF_NONE;
 ch->prev_hop_ = index;          // AODV hack
 
 th->selfID = index;                                                               // new
 th->current_pos_x = mnode->X_;		                                          //获取本身坐标后在拓扑控制头中广播出去
 th->current_pos_y = mnode->Y_;
 th->speed = mnode->speed_;    	                                                   // really need???
 /*
 th->dest_pos_x =?
 th->dest_pos_y =?
 */
  


 ih->saddr() = index;
 ih->daddr() = IP_BROADCAST;
 ih->sport() = RT_PORT;
 ih->dport() = RT_PORT;
 ih->ttl_ = 1;

 Scheduler::instance().schedule(target_, p, 0.0);
}


void
// #include <math.h> 
AODV::recvHello(Packet *p) {
//struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_topocontrol *th = HDR_AODV_TOPOCONTROL(p);                     //new
struct hdr_aodv_reply *rp = HDR_AODV_REPLY(p);
struct hdr_aodv_announce  *anch = HDR_AODV_ANNOUNCE(p);
 

double Angle;
double Angle1;
double Angle2;
MobileNode *mnode = new MobileNode;
AODV_Neighbor *nb;

Angle = ComptAngle(th->current_pos_x,th->current_pos_y,mnode->X_,mnode->Y_);  //本节点坐标x,y 调用函数comptAngle，得到Angle   
        
 nb = nb_lookup(rp->rp_dst);  
 if(nb == 0) {
   nb_insert(rp->rp_dst);
   nb->nb_angle = Angle;                                       //在邻居列表里添加角度栏及坐标栏(在aodv_rtable中声明了)
   nb->nb_current_x = th->current_pos_x;
   nb->nb_current_y = th->current_pos_y;                                      
 }
 else {
   nb->nb_expire = CURRENT_TIME +
                 (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL);              // HELLO_INTERVAL=1000ms 考虑节点运动速度 需要动态更新？

   nb->nb_angle = Angle;                                                  // new   update  
   nb->nb_current_x = th->current_pos_x;                                  //really need?
   nb->nb_current_y = th->current_pos_y;                       
 }
AODV_Neighbor *nb1 = nbhead.lh_first;
AODV_Neighbor *nb2 = nbhead.lh_first;

 for(; nb1; nb1 = nb1->nb_link.le_next) {
 for(nb1->nb_link.le_next; nb2; nb2 = nb2->nb_link.le_next) {	
   Angle1 = nb1->nb_angle; 
   Angle2 = nb2->nb_angle;
    
 if((fabs(Angle1 - Angle2) >= 90) &&  (fabs(Angle1 - Angle2) <= 270)){
 sendAnnounce(nb1->nb_addr,nb2->nb_addr);                          // 夹角大于90 调用Announce函数来使nb1和nb2删除邻居
 }
 }
// return nb1，nb2;?
}
 
// 计算与邻居的距离，调用动态调整发射功率函数

 Packet::free(p);   //  更新邻居列表
}

void 
AODV::sendAnnounce(nsaddr_t id1,nsaddr_t id2){
Packet *p = Packet::alloc();
struct hdr_ip *ih = HDR_IP(p);
struct hdr_aodv_announce  *anch = HDR_AODV_ANNOUNCE(p);
 
#ifdef DEBUG
fprintf(stderr, "sending Announce from %d at %.2f\n", index, Scheduler::instance().clock());
#endif // DEBUG

 anch->anc_type = AODVTYPE_ANNOUNCE;
 anch->delete_id1 = id1;
 anch->delete_id2 = id2;
 ih->saddr() = index;
 ih->daddr() = IP_BROADCAST;
 ih->sport() = RT_PORT;
 ih->dport() = RT_PORT;
 ih->ttl_ = 1;

 Scheduler::instance().schedule(target_, p, 0.0);
 }
	
void	
AODV::recvAnnounce(Packet *p){
struct hdr_aodv_topocontrol *th = HDR_AODV_TOPOCONTROL(p); 
struct hdr_aodv_announce   *anch = HDR_AODV_ANNOUNCE(p);
AODV_Neighbor *nb;
  if(th->selfID == anch->delete_id1){
	nb = nb_lookup(anch->delete_id2);
	nb_delete(anch->delete_id2);
}
  else(th->selfID == anch->delete_id2){
 	nb = nb_lookup(anch->delete_id1);
	nb_delete(anch->delete_id1);
}
//都不是就什么都不做 需要写？
Packet::free(p);
}


void
AODV::nb_insert(nsaddr_t id) {

AODV_Neighbor *nb = new AODV_Neighbor(id);

 assert(nb);

 nb->nb_expire = CURRENT_TIME +
                (1.5 * ALLOWED_HELLO_LOSS * HELLO_INTERVAL);
 LIST_INSERT_HEAD(&nbhead, nb, nb_link);
 seqno += 2;             // set of neighbors changed
 assert ((seqno%2) == 0);

}


AODV_Neighbor*
AODV::nb_lookup(nsaddr_t id) {
AODV_Neighbor *nb = nbhead.lh_first;

 for(; nb; nb = nb->nb_link.le_next) {
   if(nb->nb_addr == id) break;
 }
 return nb;
}


/*
 * Called when we receive *explicit* notification that a Neighbor
 * is no longer reachable.
 */
void
AODV::nb_delete(nsaddr_t id) {
AODV_Neighbor *nb = nbhead.lh_first;

 log_link_del(id);
 seqno += 2;     // Set of neighbors changed
 assert ((seqno%2) == 0);

 for(; nb; nb = nb->nb_link.le_next) {
   if(nb->nb_addr == id) {
     LIST_REMOVE(nb,nb_link);
     delete nb;
     break;
   }
 }

 handle_link_failure(id);

}


/*
 * Purges all timed-out Neighbor Entries - runs every
 * HELLO_INTERVAL * 1.5 seconds.
 */
void
AODV::nb_purge() {
AODV_Neighbor *nb = nbhead.lh_first;
AODV_Neighbor *nbn;
double now = CURRENT_TIME;

 for(; nb; nb = nbn) {
   nbn = nb->nb_link.le_next;
   if(nb->nb_expire <= now) {
     nb_delete(nb->nb_addr);
   }
 }

}
//  计算距离调用 mobilenode类中 double   MobileNode::distance(MobileNode *m)算出与邻居的距离