aodv.cc

linux平台下,在ns2里面实现的基于价格的分布式优化算法源代码

// Yuan : what if the view hop changes?
void
AODV::view_update (struct hdr_aodv_hello * rh) {
    AODV_View* view;
    printf("AODV: %d view_update on hello\n", index);
   //deal the the nb information first 
   /* Yuan comments temp
    view = view_lookup (index,rh->rh_src);
    
    if (view == NULL) {
	    view = new AODV_View(index,rh->rh_src,0,CURRENT_TIME);
        assert(view);
        view->one_hop = 0;
        view->other_hop = 1;
		view->hop_timestamp = CURRENT_TIME; //?
		LIST_INSERT_HEAD(&vhead, view, view_link);
    } else {
        view->view_timestamp = CURRENT_TIME;
    }
    */
    for (int k=0; k <rh->rh_view_num; k++) {
        view = view_lookup (rh->rh_one[k],rh->rh_other[k]);
        if (view == NULL) {
			view = new AODV_View(rh->rh_one[k],rh->rh_other[k],rh->rh_grad[k],rh->rh_timestamp[k]);
			assert(view);
			
			int one_hop = hopview_lookup(rh->rh_one[k]);
			view->one_hop= (one_hop <= rh->rh_one_hop[k]+1)? one_hop: rh->rh_one_hop[k]+1;
			int other_hop = hopview_lookup(rh->rh_other[k]);
			view->other_hop= (other_hop <= rh->rh_other_hop[k]+1)? other_hop: rh->rh_other_hop[k]+1;
			view->hop_timestamp = rh->rh_timestamp[k]; 
			LIST_INSERT_HEAD(&vhead, view, view_link);
        } else{
            if (view->view_timestamp < rh->rh_timestamp[k]) {
                view->view_grad = rh->rh_grad[k];
                view->view_timestamp = rh->rh_timestamp[k];
            }
			//Yuan note
			//if (hop_expire > CURRENT_TIME) {
			//not expire
			//int one_hop = hopview_lookup(rh->rh_one[k]);
			//int other_hop = hopview_lookup(rh->rh_other[k]);
			//view->one_hop= (one_hop <= rh->rh_one_hop[k]+1)? one_hop: rh->rh_one_hop[k]+1;
			//view->other_hop= (other_hop <= rh->rh_other_hop[k]+1)? other_hop: rh->rh_other_hop[k]+1;
        }
    }
    view_print();

    /* check whether this is a transmiting node, if it is,it calculates the
      price*/
    
    AODV_Neighbor *nb = nbhead.lh_first;
    int tx_node = 0;
    for(; nb; nb = nb->nb_link.le_next) {
        if(nb->nb_aggr_rate > 0) {
            tx_node = 1;
            break;
        }
    }
    //Yuan add temp
    tx_node = 1;
    if (tx_node){
        price_update();
    }
}

AODV_View*
AODV::view_lookup(nsaddr_t one, nsaddr_t other) {
    AODV_View *view = vhead.lh_first;

    for (;view; view = view->view_link.le_next) {
        if( isSameLink(view->view_one, view->view_other, one, other)) break;
    }
    return view;
}
	
void
AODV::view_delete(nsaddr_t one, nsaddr_t other) {

    AODV_View *view = vhead.lh_first;

    for(; view; view = view->view_link.le_next) {
        if( isSameLink(view->view_one, view->view_other, one, other)) {
            LIST_REMOVE(view,view_link);
            delete view;
            break;
        }
    }
    //Yuan new change
    //price_update();
}

void
AODV::view_purge() {
AODV_View *view = vhead.lh_first;
AODV_View *viewn;
double now = CURRENT_TIME;
double view_expire;

    for(; view; view = viewn) {
        viewn = view->view_link.le_next;
        view_expire = view->view_timestamp + ALLOWED_HELLO_LOSS * VIEW_INTERVAL;
        if(view_expire <= now) {
            printf("view at %d (%d, %d) purged\n",index, view->view_one, view->view_other);
            view_delete(view->view_one, view->view_other);
        }
    }
}
void
AODV::view_print() {
    AODV_View *view = vhead.lh_first;

    for (;view; view = view->view_link.le_next) {
        printf("%d view: (%d:%d,%d:%d): %f at %f\n",index, view->view_one, view->one_hop,view->view_other,view->other_hop, view->view_grad, view->view_timestamp);
    }
}

void
AODV::price_update() {
//  if inter = 2* tx
    if (NUM_COMM_HOP<=2)
    	clique_price_update_one_hop();
    else
	    clique_price_update();

    AODV_Neighbor *nb = nbhead.lh_first;    
    for (;nb; nb = nb->nb_link.le_next) {
        nb_price_update(nb);
    }    
}

#ifdef CENTRAL
void 
AODV::direct_price_update(struct hdr_aodv_hello * rh) {
    printf("AODV: %d direct_price_update from %d\n",index,rh->rh_src);
    AODV_Clique* clique;
	for (int i = 0; i < rh->rh_clique_num; i++) {
		for (clique = cliquehead.lh_first;clique; clique = clique->clique_link.le_next){
			if (clique->isSameClique(rh->rh_clique_ID[i],rh->rh_clique_num_subflow[i])){
				clique->clique_price = rh->rh_clique_price[i];
				clique->clique_tag = 0; // a slave;
			}
		}
	}
//    clique_print();
}
#endif

void
AODV::clique_price_update_one_hop () {
    printf("AODV: clique_price_update_one_hop \n");
    AODV_View *subflows[MAX_VIEW_PER_NODE]; 
	double clique_grad = 0;
    int i = 0; 
    AODV_View *view = vhead.lh_first;
	for(; view; view = view->view_link.le_next) {
		subflows[i] = view;
		i++;
        clique_grad += view->view_grad;
	}
    int count = i;
    double old_price = INIT_CLIQUE_PRICE;
    AODV_Clique *clique = cliquehead.lh_first;
    if (clique) {
        old_price = clique->clique_price;
        if (clique->isSameClique(subflows,count)){
            clique->clique_price += GAMMA * clique_grad;     
            if (clique->clique_price < 0 )
                clique->clique_price = 0;
        } else {
            AODV_Clique *new_clique = new AODV_Clique(subflows,count, this);
            assert(new_clique);
            new_clique->clique_price = old_price;
            new_clique->clique_price += GAMMA * clique_grad;     
            if (new_clique->clique_price < 0 )
                new_clique->clique_price = 0;
            LIST_REMOVE(clique,clique_link);
            delete clique;
            LIST_INSERT_HEAD(&cliquehead, new_clique, clique_link);
        }
    } else {
        AODV_Clique *new_clique = new AODV_Clique(subflows,count,this);
        assert(new_clique);
        new_clique->clique_price = old_price;
        new_clique->clique_price += GAMMA * clique_grad;     
        if (new_clique->clique_price < 0 )
            new_clique->clique_price = 0;
        LIST_INSERT_HEAD(&cliquehead, new_clique, clique_link);
    }
//    clique_print();
}
void
AODV::clique_price_update() {
    printf("AODV: %d clique_price_update\n",index);
	
    AODV_View *subflows[MAX_VIEW_PER_NODE]; 
    char significance[MAX_VIEW_PER_NODE];
	char *flag; 
	AODV_View *view = vhead.lh_first;
    int num_flows = 0;

	//generate the subflow array
	int i=0;

	for(; view; view = view->view_link.le_next) {
		subflows[i] = view;
		i++;
	}

	//tranverse all the (sub)sets of subflows
	num_flows = i;
    if (num_flows ==0)
        return;
    flag = new char[(int)pow(2,num_flows)]; 
    
    for(i = (int)pow(2,num_flows) - 1; i > 0; i--) {
		flag[i] = 1;
	}

	for(i = (int)pow(2,num_flows) - 1; i > 0; i--) {
		if (flag[i]){

        	// Rebuild Candidate Clique Array
        	AODV_View** clique_cand = new AODV_View*[num_flows];
        	int count = 0;

        	for (int j = 0; j < num_flows; j ++)
				if ((i >> j) % 2){
					clique_cand[count] = subflows[j];
    				count ++;
	    		}

			double clique_grad;
		
			if (isClique(clique_cand,count, &clique_grad)) {
         
                int isoldclique = 0;
                int iscontained = 0;
                AODV_Clique *clique;
                
                //is it an existing clique?
                for (clique = cliquehead.lh_first;clique; clique = clique->clique_link.le_next){
                //Yuan Note central
                    if (clique->isSameClique(clique_cand,count)){
				    //    if (clique->clique_tag == 1) {
                            clique->clique_price += GAMMA * clique_grad;     
                            if (clique->clique_price < 0 )
                                clique->clique_price = 0;
                    //    }
                        isoldclique = 1;
                        break;
				    }
                }
                if (!isoldclique) {
                //if it is a new clique;
                
                //is the new clique_cand contained in an old one?
                AODV_Clique *new_clique = new AODV_Clique(clique_cand,count,this);
                assert(new_clique);
                for (clique = cliquehead.lh_first;clique; clique = clique->clique_link.le_next){
                    if (contain(clique,new_clique)) {
                        isoldclique = 1;
                        printf("old containts new\n");
                        delete new_clique;
                        iscontained = 1;
                        break;
                    }
                }

                if (!iscontained) {
                //    AODV_Clique *new_clique = new AODV_Clique(clique_cand,count,this);
                //    assert(new_clique);
					//remove old cliques that is contained by this new clique
                        
                    AODV_Clique *cliquen;
					for (clique = cliquehead.lh_first;clique; clique = cliquen){
                        cliquen = clique->clique_link.le_next;
						if (contain(new_clique,clique)){
                            new_clique->clique_price = clique->clique_price;
                            LIST_REMOVE(clique,clique_link);
                            delete clique;
						}
					}

                    new_clique->clique_price += GAMMA * clique_grad;     
                    if (new_clique->clique_price < 0 )
                        new_clique->clique_price = 0;
                    printf("at %d, new clique new price %f\n",index,new_clique->clique_price);

                    LIST_INSERT_HEAD(&cliquehead, new_clique, clique_link);
                }
                
				// Mark all sub-cliques to avoid recalculation
				int count = 0;
				for (int j = 0; j < num_flows; j ++)
					if ((i >> j) % 2){
						significance[count] = j;
						count ++;
					}

				for (int j = 1; j < (int)pow(2, count); j ++){
					int num = 0;
					for (int k = count - 1; k >= 0; k --)
						if ((j >> k) % 2)
							num += 1 << significance[k];
					flag[num] = 0;
				}
                }
			} //if
            delete clique_cand;
		} //if 
	} //for
    delete flag;
//    clique_print();
}

void
AODV::clique_print() {
    AODV_Clique *clique = cliquehead.lh_first;
    for (; clique; clique = clique->clique_link.le_next) {
        printf("%d clique_ID:",index);
        for (int i=0; i< 2*clique->clique_num_subflow; i+=2) {
            printf("[%d,%d];",clique->clique_ID[i],clique->clique_ID[i+1]);
        }
        printf("; Qprice: %f; tag %d\n",clique->clique_price,clique->clique_tag);
    }
}

void
AODV::nb_price_update(AODV_Neighbor* nb) {
    nb->nb_price = 0;
    AODV_Clique *clique = cliquehead.lh_first;
    for (; clique; clique = clique->clique_link.le_next) {
        if (viewinClique(clique,index,nb->nb_addr))
            nb->nb_price += clique->clique_price;
    }
    nb->nb_flag = 1;
}
    	
double  
AODV::get_price(nsaddr_t nexthop) {
    AODV_Neighbor* nb = nb_lookup(nexthop);
    if(nb==NULL){
        printf("get_price: %d can not find nb %d \n",index,nexthop);
        return 0;
    }
    return nb->nb_price;
}

int 
AODV::get_flag(nsaddr_t nexthop){
	AODV_Neighbor* nb = nb_lookup(nexthop);
    if(nb==NULL){
        printf("get_flag: %d can not find nb %d \n",index,nexthop);
        return 0;
    }
    return nb->nb_flag;
}

double
AODV::get_grad(nsaddr_t nexthop){
	AODV_Neighbor* nb = nb_lookup(nexthop);
    if(nb==NULL){
        printf("get_grad: %d can not find nb %d \n",index,nexthop);
        return 0;
    }
    return nb->nb_grad;
}

/* return 0, if it is not a clique
 * otherwise, return 1 and the aggregated grad  within the clique in clique_grad
 */

int
AODV::isClique(AODV_View **clique, int count, double *clique_grad) {
    printf("AODV: isClique\n");

	*clique_grad = 0;

    //Yuan for interferece> tx use 2, otherwise use 1
    if (NUM_COMM_HOP <=2){
	    for (int j = 0; j < count; j++)
		    *clique_grad += clique[j]->view_grad;
        return 1;
    }
	// If any pair of subflows are not contended, return 0
	// Otherwise, return 1
	for (int j = 0; j < count; j ++)
		for (int k = j+1; k < count; k ++)
			if (!isContend(clique[j]->view_one, clique[j]->view_other, clique[k]->view_one, clique[k]->view_other))
				return 0;

	for (int j = 0; j < count; j++)
		*clique_grad += clique[j]->view_grad;
    printf("AODV: %d isClique: clique_grad %f\n",index, *clique_grad);

	return 1;
}

int
AODV::isContend(nsaddr_t a_one, nsaddr_t a_other, nsaddr_t b_one, nsaddr_t b_other) {
	if ((a_one == b_one)||(a_other == b_other)||(a_one == b_other)||(a_other == b_one)) 
		return 1;
	if (view_lookup(a_one, b_one)||view_lookup(a_one, b_other)||view_lookup(a_other, b_one)||view_lookup(a_other, b_other))
		return 1;
	return 0;
}

int
AODV::isSameLink(nsaddr_t a_one, nsaddr_t a_other, nsaddr_t b_one, nsaddr_t b_other) {
	return ((a_one == b_one)&&(a_other == b_other)) ||((a_one == b_other)&&(a_other == b_one));
}

int
AODV::hopview_lookup(nsaddr_t addr) {
    if (addr == index)
        return 0;
	AODV_View *view = vhead.lh_first;
	for(; view; view = view->view_link.le_next) {
		if (view->view_one == addr)
			return view->one_hop;
		if (view->view_other == addr)
			return view->other_hop;
	}
	//return a large integer
	return 10;
}


AODV_Clique::AODV_Clique (AODV_View **subflow, int num_subflow, AODV *rap) {
    ra = rap;
    clique_num_subflow = num_subflow;
	int small_one = LARGE_INT8;
	int small_other = LARGE_INT8;
	int	small_index = -1;
	int temp_one, temp_other;
	char *flag;
    clique_tag = 1;
    
    flag = new char[num_subflow]; 
    
    for(int i = 0; i < num_subflow; i++) {
		flag[i] = 1;
	}


	for (int j = 0; j< 2*num_subflow; j+=2) {
	    small_one = LARGE_INT8;
	    small_other = LARGE_INT8;
        small_index = -1;
		for (int i = 0; i< num_subflow; i++) {
			if (flag[i]) {

				//make sure _one is smaller than _other
				if (subflow[i]->view_one > subflow[i]->view_other) {
					temp_one = subflow[i]->view_other;
					temp_other = subflow[i]->view_one;
				}else{
					temp_one = subflow[i]->view_one;
					temp_other = subflow[i]->view_other;
				}

				//pick the smallest
				if ((temp_one< small_one)|| ((temp_one == small_one)&&(temp_other< small_other))){
					small_index = i;
					small_one = temp_one;
					small_other = temp_other;
				}
			}
		}
		flag[small_index] = 0;
		clique_ID[j]=small_one;
		clique_ID[j+1] = small_other;
	}
        
    //clique_price = Random::random()% 4;//?
    clique_price = INIT_CLIQUE_PRICE;
    delete flag;
}
   
int    
AODV_Clique::isSameClique(AODV_View **subflow, int num_subflow) {
    int match = 0;
    if (num_subflow != clique_num_subflow)
            return 0;
    for (int i = 0; i<num_subflow; i++) {
        match =  0;
        for (int j = 0; j < 2*clique_num_subflow; j+=2) {
            if (ra->isSameLink(subflow[i]->view_one, subflow[i]->view_other,
            clique_ID[j], clique_ID[j+1])) {
                match = 1;
                break;
            }
        }
        if (!match)
            return 0;
    }
    return 1;
}

   
int    
AODV_Clique::isSameClique(char* clique_ID_2,int clique_num_subflow_2) {
	if (clique_num_subflow != clique_num_subflow_2)	
		return 0;
	for (int i = 0; i <2*clique_num_subflow; i++) {
		if (clique_ID[i]!=clique_ID_2[i])
			return 0;
    }
	return 1;
}

int
AODV::viewinClique(AODV_Clique *q, nsaddr_t one,nsaddr_t other) {
	for (int i =0; i < 2*q->clique_num_subflow; i+=2) {
		if (isSameLink(q->clique_ID[i],q->clique_ID[i+1], one, other))
			return 1;
	}
	return 0;
}

int
AODV::contain(AODV_Clique *clique, AODV_Clique *q) {
	for (int i=0; i< 2*q->clique_num_subflow; i+=2) {
		if (!viewinClique(clique, q->clique_ID[i],q->clique_ID[i+1]))
			return 0;
	}
	return 1;
}