基于MCKP-MMF算法的无线传感器网络流量估计Matlab仿真

一、理论基础

无线传感器网络(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;       endend 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半径请求变化');1.2.3.4.5.6.7.8.9.10.11.12.13.14.15.16.17.18.19.20.21.22.23.24.25.26.27.28.29.30.31.32.33.34.35.36.37.38.39.40.41.42.43.44.45.46.47.48.49.50.51.52.53.54.55.56.57.58.59.60.61.62.63.64.65.66.67.68.69.70.71.72.73.74.75.76.77.78.79.80.81.82.83.84.85.86.87.88.89.90.91.92.93.94.95.96.97.98.99.100.101.102.103.104.105.106.107.108.109.110.111.112.113.114.115.116.117.118.119.120.121.122.123.124.125.126.127.128.129.130.131.132.133.134.135.136.137.138.139.140.141.142.143.

三、仿真测试结果

免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删