SPIN Routing Algorithm

平面路由協定仿真——SPIN算法

仿真軟體——MATLAB

1、定位算法的實作

1.1 基本原理

SPIN協定是一種以資料為中心的自适應通信路由協定，假設所有傳感器節點都可能是希望獲得資料的彙聚節點，每個傳感器節點都知道自己是否需要資料。為了避免防洪法出現的資訊爆炸問題和部分重疊現象，傳感器節點在傳送資料之前彼此使用中繼資料進行協商，協商機制可確定傳輸有用資料。中繼資料的定義格式是與具體應用相關的，SPIN協定沒有給出它的具體定義格式。SPIN協定的有點是采用協商機制，避免了資源的盲目使用，但在某種情況下，他會出現資料不可傳遞性的問題。

SPIN協定有3 種類型的消息，即ADV、REQ和DATA

1）ADV——用于新資料廣播。當一個節點有資料需要傳輸時，它可以用ADV資料包對外廣播；

2）REQ——用于請求發送資料。當一個節點希望接收DATA資料包時，發送REQ資料包；

3）DATA——資料包。包含了附上中繼資料頭的傳感器采集的資料的資料包。

1.2 代碼實作

1.2.1 prepare.m

n=100;
spread=0.2;
X=rand(n, 1);
Y=rand(n, 1);
start_index=randi(n);
end_index=randi(n);
hold on
plot(X, Y, '.', 'markersize', 20);
plot(X(start_index), Y(start_index), 'm.', 'markersize', 20);
plot(X(end_index), Y(end_index), 'm.', 'markersize', 20);

save X;
save Y;
save spread;
save start_index;
save end_index;      

1.2.2 spin.m

end_index=load('end_index.mat');
X=end_index.X;
Y=end_index.Y;
spread=end_index.spread;
start_index=end_index.start_index;
end_index=end_index.end_index;
n=length(X);
times=zeros(n, 1);
found=zeros(n, 1);
for i=1:n
    for j=1:n
        dmat(i,j)=sqrt((X(i)-X(j))^2+(Y(i)-Y(j))^2);
    end
end
queue=zeros(n*100, 1);
queue(1)=start_index;
found(start_index)=1;
front=2;
rear=1;
hold on;
plot(X, Y, 'o');
while found(end_index)==0 && rear<front
    for i=1:n
        if i~=queue(rear) && dmat(queue(rear), i)<=spread && found(i)==0
            line([X(queue(rear)),X(i)], [Y(queue(rear)),Y(i)]);
            queue(front)=i;
            found(i)=1;
            times(i)=times(i)+1;
            front=front+1;
        end
    end
    rear=rear+1;
end
for i=1:n
    if times(i)<=5
        plot(X(i), Y(i), '.', 'markersize', 20);
    elseif times(i)<=10
        plot(X(i), Y(i), 'g.', 'markersize', 20);
    elseif times(i)<=20
        plot(X(i), Y(i), 'c.', 'markersize', 20);
    elseif times(i)<=50
        plot(X(i), Y(i), 'y.', 'markersize', 20);
    elseif times(i)<=100
        plot(X(i), Y(i), 'k.', 'markersize', 20);
    else
        plot(X(i), Y(i), 'r.', 'markersize', 20);
    end
end
plot(X(start_index), Y(start_index), 'm.', 'markersize', 20);
plot(X(end_index), Y(end_index), 'm.', 'markersize', 20);
disp(sum(times));      

2、仿真結果和分析

2.1 仿真結果