assignment1.asv

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

clear;
max_t=zeros(5,1);
max_f=zeros(5,1);
inc=1;
for N=100:100:500
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;
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
   n(i)=n(i)-1;
end
hop=N*ones(N,1);hop(1)=0;k=0;computed=1;visited=zeros(N,1);d=0;
while computed<=N 
    for i=1:N
        for j=1:n(i)
             if hop(neighbour(i,j))==k && visited(i)==0
                hop(i)=k+1;
                visited(i)=1;
                computed=computed+1;
             end
             d=d+1;
        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)
        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
for i=1:N
    c(i)=c(i)-1;
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
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(inc)=1;max_f(inc)=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;
           l(u)=0;
           for i=1:b(u)
               l(u)=l(u)+1;
               d(u,l(u))=brother(u,i);
           end
           for i=1:n(parent(u))
               l(u)=l(u)+1;
               d(u,l(u))=neighbour(parent(u),i);
           end
           for i=1:n(u)
               for j=1:c(neighbour(u,i))
                   l(u)=l(u)+1;
                   d(u,l(u))=children(neighbour(u,i),j);
               end
           end
           l(u)=l(u)+1;
           d(u,l(u))=parent(u);
           while i~=l(u)+1
                i=1;
                while i<=l(u)
                    if  p==t(d(u,i))
                        p=p+1;
                        break;
                    end
                    i=i+1;
                end
           end
          t(u)=p;f(u)=q;
          if t(u)>max_t(inc)
          max_t(inc)=t(u);
          end
          if f(u)>max_f(inc)
             max_f(inc)=f(u);
          end
          visited(u)=1; 
          k=k+1;
          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
inc=inc+1;
end