無線傳感器網絡基于MCKP-MMF算法的流量估計matlab仿真

目錄

​​一、理論基礎​​

​​二、核心程式​​

​​三、仿真測試結果​​

作者ID  ：fpga和matlab

擅長技術：
1.無線基帶,無線圖傳,編解碼 
2.機器視覺,圖像處理,三維重建 
3.人工智能,深度學習 
4.智能控制,智能優化
5.其他      

一、理論基礎

       無線傳感器網絡(Wireless Sensor Networks, WSN)是一種分布式傳感網絡，它的末梢是可以感覺和檢查外部世界的傳感器。WSN中的傳感器通過無線方式通信，是以網絡設定靈活，裝置位置可以随時更改，還可以跟網際網路進行有線或無線方式的連接配接。通過無線通信方式形成的一個多跳自組織網絡。       

       無線傳感器網絡（Wireless sensor network）是由大量靜止/移動的傳感器以自組織和多跳的方式構成無線網絡。目的是協作地探測、處理、傳輸網絡覆寫區内感覺對象的監測資訊，并報告給使用者。相較于傳統式的網絡和其他傳感器相比，無線傳感器網絡有以下特點：

（1）組建方式自由。無線網絡傳感器的組建不受任何外界條件的限制，組建者無論在何時何地，都可以快速地組建起一個功能完善的無線網絡傳感器網絡，組建成功之後的維護管理工作也完全在網絡内部進行。

（2）網絡拓撲結構的不确定性。從網絡層次的方向來看，無線傳感器的網絡拓撲結構是變化不定的，例如構成網絡拓撲結構的傳感器節點可以随時增加或者減少，網絡拓撲結構圖可以随時被分開或者合并。

（3）控制方式不集中。雖然無線傳感器網絡把基站和傳感器的節點集中控制了起來，但是各個傳感器節點之間的控制方式還是分散式的，路由和主機的功能由網絡的終端實作各個主機獨立運作，互不幹涉，是以無線傳感器網絡的強度很高，很難被破壞。

（4）安全性不高。無線傳感器網絡采用無線方式傳遞資訊，是以傳感器節點在傳遞資訊的過程中很容易被外界入侵，進而導緻資訊的洩露和無線傳感器網絡的損壞，大部分無線傳感器網絡的節點都是暴露在外的，這大大降低了無線傳感器網絡的安全性。

       下面我們考慮具有個節點的集合，以及具有個通路點的集合。基于此，節點與通路點之間的通信可以用圖表示，在中兩個節點之間存在一條邊當且僅當它們之間的距離小于某一常數值。請注意我們不考慮通路點之間的直接通信，是以。每個節點具有有限可量化的資源用于為某些通路點傳送資料。需要為某個通路點配置設定資源的節點集合記為。為了定義通路點的本地影響範圍，我們需要引入，我們稱之為通路點半徑，通路點與中距離其最遠的節點的跳數。通路點半徑從某種程度上反應了通路點對網絡的影響力，或該通路點的效用。對于每個通路點以及其半徑，我們可以定義一個向量：

       基于流量估計，MCKP-MMF算法便可以找到本地MCKP-MMF的近似解。其基本思想與MMKP-MMF相似，但是相比之下，MCKP-MMF采取了更為簡單的政策進而使之成為一種啟發式算法并且運作更快。算法從最小配置開始，并将所有通路點初始化為活動狀态。此後，算法在執行的每一輪中發現一個較好的部分解，并将相關的通路點置為停止狀态，直至所有通路點都成為停止狀态，算法終止。選擇較好的部分解的政策與文獻類似，

       于最佳回報（savings）的政策。實際上，流量矩陣中的元素可以被看作為一個回報函數。當然，回報函數在此可以更确切的描述為代價函數，表示對于某個通路點，其影響半徑從變化為時，給節點帶來的額外負擔。是以，MCKP-MMF算法可以通過每次選擇代價最小的通路點并增加其影響半徑，進而 取得近似最優配置。

       算法的基本過程如圖所示。該算法的輸入為對該節點産生影響的通路點。因為該算法在每個節點上執行，是以隻需要單一的帶寬限制條件，即該節點的帶寬。其中的sort函數對（活動通路點集合）中的通路點按其代價 以升序排序。最後，函數feasible檢測限制條件是否被違反。

       算法在執行的第輪檢驗将所有活動通路點的影響半徑從增加到是否可以得到一個合适解。增加每個活動通路點的影響半徑将按照與之對應的代價由小到大進行，即總是優先增加那些代價最小的通路點半徑。如果所有活動通路點的半徑都被增加且所得為合适解，則算法進入下一輪計算。否則，第一個違反限制條件的通路點以及其後所有通路點将被标記為停止狀态，而後算法進入下一輪計算。

       某個通路點可能先後收到來自多個擁塞節點的重新設定影響半徑的要求，此時為了滿足帶寬消耗最大的節點的帶寬限制，通路點需要将其新影響半徑設定為其中最小的一個。一種簡單的方法是每次收到這樣的請求之後，将其中包含的新影響半徑與通路點目前影響半徑比較，如果新影響半徑較小則修改目前影響半徑為新影響半徑，否則通路點保持目前影響半徑。這樣作的一個副作用是通路點的影響半徑将随時間增長而變小。從另一方面，節點由于僅通過本地資訊為與之相關的通路點确定影響半徑，可能無法得到通路點真正的最優影響半徑。為了消除這個副作用并幫助通路點跳出本地最優狀态進而更接近全局最優配置，每個通路點需要周期性的增加其影響半徑。

二、核心程式

clc;
clear;
close all;
warning off;
RandStream.setDefaultStream(RandStream('mt19937ar','seed',41));


%參數初始化
Scale = 100;           %場景範圍
N     = 50;            %節點數目 
M     = 8;             %設定通路節點，為了便于觀察，我們設定點數較少，這樣可以将所有波形繪制出來
SATV  = 1;             %給每個資源點的飽和值
R_ini = 0.5;           %定義初始半徑
Step  = 0.1;           %慢啟動階段半徑增加步進
FLag  = zeros(M,1);    %記錄每個通路節點的狀态，0為第一階段，1為第二階段
SATVs = SATV*ones(1,N);
Requst= zeros(M,N);
saturated_state = cell(M,N);
 
%産生n個節點
[Xn,Yn] = func_node_gen(N,Scale);
%産生M個通路節點
[Xm,Ym] = func_node_gen(M,Scale);

figure(1);
subplot(121);
plot(Xn,Yn,'bo');
title('資源點');
axis square;
axis([-5,Scale+5,-5,Scale+5]);
subplot(122);
plot(Xn,Yn,'bo');
hold on;
plot(Xm,Ym,'ro');
hold off;
legend('資源點','通路點');
title('所有點');
axis square;
axis([-5,Scale+5,-5,Scale+5]);

%每個通路節點針對不同資源節點的資源需求
for i = 1:M
    for j = 1:N
        Requst(i,j) = 0.5;   
    end
end
 
Stimes = 400;
R      = zeros(M,Stimes);
cut    = zeros(1,Stimes);
%下面開始循環
times = 0;
while(times < Stimes)
     figure(2);
     plot(Xn,Yn,'b.');
     hold on;
     plot(Xm,Ym,'r.');
     hold on;    
     
     times
     times = times + 1;
     SATVs = SATV*ones(1,N);
     
     %每個資源節點進行發送請求,初始條件
     for j = 1:M
         %表示該通路點處于第1階段
         if FLag(j) == 0
            R_ini    = R_ini + Step; 
            query(j) = R_ini; 
            %計算每個節點到通路點的距離
            for i1 = 1:N 
                d = sqrt( (Xn(i1) - Xm(j))^2 + (Yn(i1) - Ym(j))^2 );
                %判斷是否在一定範圍之内
                if d <= R_ini
                   %進行資源配置設定
                   SATVs(1,i1) = SATVs(1,i1) - Requst(j,i1);
                else
                   SATVs(1,i1) = SATVs(1,i1); 
                end    
                %每次請求完之後，判斷是否擁堵
                if SATVs(1,i1) <= 0%表示擁堵
                   saturated_state{j,i1} = [1,R_ini,Xm(j),Ym(j),Xn(i1),Yn(i1)]; 
                   FLag(j) = 1;
                else
                   saturated_state{j,i1} = [0,0,0,0,0,0];  
                   FLag(j) = FLag(j);
                end
            end 

         end

         %表示該通路點處于第2階段
         if FLag(j) == 1
             
            %請求半徑為某一較小值以試圖緩解擁塞
            R_ini    = R_ini - Step;
            query(j) = R_ini; 
            %計算每個節點到通路點的距離
            %計算每個節點到通路點的距離
            for i1 = 1:N 
                d = sqrt( (Xn(i1) - Xm(j))^2 + (Yn(i1) - Ym(j))^2 );
                %判斷是否在一定範圍之内
                if d > R_ini & saturated_state{j,i1}(1) == 1
                   %進行資源配置設定
                   SATVs(1,i1) = SATVs(1,i1) + Requst(j,i1);
                else
                   SATVs(1,i1) = SATVs(1,i1); 
                end    
                %每次請求完之後，判斷是否擁堵
                Len = length(find(SATVs(1,:) > 0));
                if Len == N
                   FLag(j) = 0;
                else
                   FLag(j) = 1; 
                end 
            end 
            cut(times) = times;
         end    
     end 
     
     %記錄各個仿真結果
     R(:,times) = query;  
     
     %動态顯示半徑變化
     for j = 1:M
         [x_,y_]=func_circle(R(j,times),Xm(j),Ym(j));
         plot(x_,y_,'k-');
         hold on
     end
     hold off;
     axis square;
     axis([-5,Scale+5,-5,Scale+5]);
     title('第一階段逐漸增加半徑，第二階段處于動态平衡');
     pause(0.0001);
end

%繪制仿真結果
figure(3);
plot(R(1,:),'b','linewidth',2);
xlabel('TIMES');
ylabel('Radius');
grid on;
title('資源點1半徑請求變化');



      

三、仿真測試結果