% Simulation prepare for IEEE conference due at 2004/01/12
% 1. 自己能random出一個connected graph
% 2. 用炳宏學長的方法改進shortest path tree
clear all;
range = 100;
radius = 30;
node_number = 30;
probability = 0.4;%%決定成為member的機率
not_connected = true;
member_ship = zeros(1,node_number);
while ( not_connected )
global_neighbor_list = zeros(node_number, node_number);
for i = 1 : node_number
node(i) = struct( 'id', i,...
'degree', 0,...
'x', ( rand(1)*range ),...
'y', ( range*rand(1) ),...
'group_member', false,...
'forwarding_node', false,...
'neighbor_list', zeros(1,node_number),...
'route_table', zeros(2,node_number),...
'degree_in_shortest_path_tree',0,...
'degree_in_our_tree',0,...
'degree_in_center_based_tree',0,...
'degree_in_multicast_center_based_tree',0,...
'visited', false );
if ( rand(1) < probability )
node(i).group_member = true;
member_ship(i) = 1;
end
end
%%建立點和點之間的連線,degree,neighbor_list, galobal_neighbor_list
%%如果任兩點之間距離小於radius應該就要有連線, 不用傳輸成功的機率決定
distance = 0;
for i=1:node_number-1
for j = i+1:node_number
distance = sqrt( ((node(i).x-node(j).x).^2) + ((node(i).y-node(j).y).^2) );
if ( distance <= radius )
node(i).degree = 1 + node(i).degree;
node(i).neighbor_list(j) = 1;
node(j).neighbor_list(i) = 1;
node(i).route_table(1, j) = j;%%建立最初始的rouing able(next hop, cost),index is destination
node(i).route_table(2, j) = 1;
node(j).route_table(1, i) = i;
node(j).route_table(2, i) =1;
%%global information
global_neighbor_list(i,j) = 1;
global_neighbor_list(j,i) = 1;
global_neighbor_list(i,i) = 1;%%close-neighbor list construction
end
end
node(i).degree = node(i).degree - 1;
end
%%建立點和點之間的連線,建立neighbor list on each node
%%judge connectivity, use DFS ot visit each point with root id =1;
temp_stack = zeros(1,node_number);
temp_top = 0;
%%push operation, push node 1 into stack
temp_top = temp_top + 1;
temp_stack( temp_top) = 1;
node(1).visited = true;
%%push operation
current_node = 0;
while (temp_top ~= 0)%%stack not empty
%%pop operation
current_node = temp_stack( temp_top);
temp_top = temp_top - 1;
%%push operation
for i = 1 : node_number
if ( node(current_node).neighbor_list(i) == 1 ) && (node(i).visited == false)
temp_top = temp_top + 1;
temp_stack( temp_top) = current_node;
temp_top = temp_top + 1;
temp_stack( temp_top) = i;
node(i).visited = true;
break;
end
end
end
not_connected = false;
for i = 1 : node_number
if (node(i).visited == false)
not_connected = true;
break;
end
end
end
%%re-initialize;prepare for other tree-based scan
for i = 1 : node_number
node(i).visited = false;
end
%% perform distance vector algorithm to find shortest path for each node
for i = 1:node_number
for j = 1:node_number
if ( node(i).route_table(2,j)~= 1 )
node(i).route_table(1,j) = NaN;%next hop
node(i).route_table(2,j) = inf;%cost
end
node(i).route_table(1,i) = i;%%自己到自己的距離是0
node(i).route_table(2,i) = 0;
end
end
%%暫存網路上的訊息
next_box = zeros(node_number,node_number);
cost_box = zeros(node_number,node_number);
for i=1:node_number
for j=1:node_number
next_box(i, j) = node(i).route_table(1, j);
cost_box(i, j) = node(i).route_table(2, j);
end
end
%implement distance vector algorithm
for message_send_times = 1 : node_number%%最少要送node_number-1次的訊息
temp_cost = zeros(1,node_number);
for i=1:node_number
for j=1:node_number
if node(i).neighbor_list(j) == 1
for k=1:node_number
temp_cost(1,k) = node(i).route_table(2, j)+cost_box(j, k);
if node(i).route_table(2,k)>temp_cost(1,k)
node(i).route_table(1,k)=j;
node(i).route_table(2,k)=temp_cost(1,k);
end
end
end
end
end%%到這邊是對每一個點作一次
%%再次發送新訊息
for i=1:node_number
for j=1:node_number
next_box(i, j) = node(i).route_table(1, j);
cost_box(i, j) = node(i).route_table(2, j);
end
end
end
%%現在每一個node都知道shortest path[destination](next hop, cost)
%%initialize multicast
shortest_tree_matrix = zeros(node_number,node_number);
source = floor(node_number*rand(1))+1;
destination = 0;
while node(source).group_member ~= 1%%select initializing source
source = floor(10*rand(1))+1;
end
%% construct shortest path tree
temp_source = source;
for i=1:node_number
if ( node(i).group_member == 1 )&& ( i ~= source )
destination = i;
while (temp_source ~= destination)
next_hop = node(temp_source).route_table(1,destination);
node(temp_source).forwarding_node = true;
shortest_tree_matrix(temp_source, next_hop) = 1;%%construct shortest path tree table
shortest_tree_matrix(next_hop, temp_source) = 1;
temp_source = next_hop;
end
end
temp_source = source;
end
for i = 1: node_number%算在shortest path tree之中的degree
for j = 1: node_number
if (shortest_tree_matrix(i, j) == 1)
node(i).degree_in_shortest_path_tree = node(i).degree_in_shortest_path_tree + 1;
end
end
end
%%這邊寫學長的algorithm
our_tree_matrix = shortest_tree_matrix;
%1.把每個在shortest path tree中的點算一次我們的degree
for i = 1 : node_number
if (node(i).degree_in_shortest_path_tree ~= 0)&&(node(i).visited == false)%%for all nodes in shortest path tree and white
for j = 1 : node_number
if ( node(i).neighbor_list(j) == 1)&&(node(j).degree_in_shortest_path_tree ~= 0)
%要加入算degree的點有:shortest path tree 的 groupmember 和forwarding
%node所以只要在tree內的degree不為0的neighbor都符合這個條件
node(i).degree_in_our_tree = node(i).degree_in_our_tree + 1;
end
end
end
end
%2.按照收集到的degree排序, 由大到小
degree_order = zeros(1,node_number);
for i = 1 : node_number
degree_order(i) = i;
end
temp = 0;
for i = 1 : (node_number - 1) ;
for j = ( i + 1 ) : node_number
if ( node(degree_order( i ) ).degree_in_our_tree < node(degree_order( j ) ).degree_in_our_tree )
temp = degree_order(i);
degree_order(i) = degree_order(j);
degree_order(j) = temp;
end
end
end
%3.由degree大的開始執行
for i = 1 : node_number
if (node(degree_order(i)).degree_in_our_tree < 3 )
continue;%只有degree>=3的才要執行, 如果degree < 3 就維持原來的shortest path tree
e