assignment.m

无线传感器网络的可靠路由算法

clear;
N=100;
M=100;
for i=1:N
    x(i)=rand(1)*M;
    y(i)=rand(1)*M;
end
x(1)=M*0.95;y(1)=M*0.95;
plot(x,y,'o',x(1),y(1),'*');
neighbour=zeros(N,N*0.2);
for i=1:N
    n(i)=1;
   for j=1:N
      if (x(i)-x(j))^2+(y(i)-y(j))^2<M^2*0.04 & i~=j
          neighbour(i,n(i))=j;
          n(i)=n(i)+1;
      end
   end
end
hop=N*ones(N,1);hop(1)=0;k=0;computed=1;visited=zeros(N,1);
while computed<=N
    for i=1:N
        for j=1:n(i)-1
             if hop(neighbour(i,j))==k && visited(i)==0
                hop(i)=k+1;
                visited(i)=1;
                computed=computed+1;
             end
        end
    end     
    k=k+1;
end
parent=ones(N,1);children=zeros(N,N*0.2);c=ones(N,1);hop(1)=0;
for i=1:N
    k=i;
    for j=1:n(i)-1
        temp=neighbour(i,j);
        if hop(temp)<hop(k) | (hop(temp)==hop(k) & c(temp)<c(k))
            k=temp;
        end
    end
    if k~=i
       parent(i)=k;
       children(k,c(k))=i;
       c(k)=c(k)+1;
    end
end
 parent(1)=1;
 for i=1:N
    if c(parent(i))~=0
       b(i)=c(parent(i))-1;
    end
   for j=1:b(i)
       brother(i,j)=children(parent(i),j);
   end
end
 for i=1:N
     cordinate_x(1)=x(i);cordinate_x(2)=x(parent(i));cordinate_y(1)=y(i);cordinate_y(2)=y(parent(i));
%     line(cordinate_x,cordinate_y);
 end
t=zeros(N,1);
f=zeros(N,1);
u=1;v=1;
t(u)=1;f(u)=1;
k=1;computed=0;
p=1;q=1;i=1;
visited=zeros(N+1,1);visited(1)=1;
max_t=1;max_f=1;d=1;
while k<N & d<20*N
    if  children(u,v)~=0 
        if visited(children(u,v))==0 
           u=children(u,v);
           p=1;q=1;i=1;
           while i~=n(u)
                i=1;
                while i<n(u)
                    if   p==t(neighbour(u,i))| p==t(parent(u))
                         p=p+1;
                         break;
                    end
                    i=i+1;
                end
           end
%       i=1;
%       while i~=n(u)
%          i=1;
%          while i<n(u)
%             if  q==f(neighbour(u,i)) 
%                q=q+1; 
%                break;
%             end
%             i=i+1;
%          end
%       end
           i=1;
           while i~=h(u)
                 i=1;
                 while i<h(u)
                    if   q==f(brother(u,i))| q==f(parent(u))
                         q=q+1; 
                         break;
                      end
                      i=i+1;
                 end
            end
%    if u==1
%        q=1;
%    else
%      while i~=b(u) 
%        i=1;
%        while i<b(u)
%            if   q==f(brother(u,i))| q==f(parent(u))| q==f(parent(parent(u)))
%               q=q+1;
%               break;
%            end
%            i=i+1;
%        end
%      end
%    end
          t(u)=p;f(u)=q;
          if t(u)>max_t
          max_t=t(u);
          end
          if f(u)>max_f
             max_f=f(u);
          end
          visited(u)=1; 
          k=k+1;
      text(x(u)+2,y(u)+2,num2str(t(u)));
%      text(x(u)-2,y(u)-2,num2str(f(u)));
          v=1;
       end
   end
      if children(u,v)==0
         u=parent(u);
         v=1;
      else if visited(children(u,v))==1 
           v=v+1;
          end
      end
   d=d+1;
end
%max_t
%max_f