zbbroadcast.m

在matlab实现的zigbee源代码

% Broadcast in ZigBee networks
% Note 1: the code looks messy, but I cannot find time to clean it up yet.
% Note 2: many other broadcast algorithms are not included.
% Note 3: the packet loss code and reliability enhancement is not included.

% References:
% G. Ding, Z. Sahinoglu, P. Orlik, J. Zhang, and B. Bhargava, Tree-Based Data Broadcast in IEEE 802.15.4 and ZigBee Networks, IEEE Transaction on Mobile Computing, 5(11): 1561-1574, 2006.
% G. Ding, Z. Sahinoglu, P. Orlik, J. Zhang, and B. Bhargava, Reliable Broadcast in ZigBee Networks, in IEEE Conference on Sensor and Ad Hoc Communications and Networks (SECON), 2005.

% Input parameters
% approach = 1, approach2 = 1, ZigBee broadcast: tree flooding + self-pruning
% approach = 1, approach2 = 2, OSR: flooding + tree self-pruning
% approach = 2, approach2 = 4, Forward node selection: OOS/ZOS: optimal solution based on N and TN(N)
% approach = 4, Global greedy

if useLQI == 1
    ps=100;  % sent power
    afa=2;  % path loss exponential
    k1=1;
    k2=10;
    gama=1; % threshold to compare LQI and LQI0
    cigma = 5;  % standard deviation of lognormal shadowing
    lasttime=zeros(maxn, 1);
    kscale = 1/500;
end

% Timer parameters
etimer=zeros(maxn, 1);
etimercount = 1;    % used when approach2 == 3, no timer case, not included in this code
etimerscale = 1;    % maximum random time out

% Self-pruning parameters:
tocover=[];
todegree=[];
if approach2 == 2
    tocover = tneighbor;    
    todegree = info(: , 4)' + 1;
elseif approach2 == 4 | approach2 == 1
    tocover = neighbor;
    todegree = info(: , 5)';
end

% Internal parameters
whilesign = 1;
toforward=[];
t1=0;   
t2=0;
F = [];
NF = [];

% Output parameters
forward=zeros(maxn, maxNeighbor+3);
% 1: status (0: initial; 1: non forward; 2: forward; 3: already forward)
% 2: if status > 0, who asked me to non-forward or forward
% 3: number of forward nodes
% 4-: my forward nodes
% numSend = 0;
numReceive = 0;
numInitial = 0;
numNonforward = 0;
numAlreadyforward = 0;
numForwardoverhead = 0;
lmine = [];
lgreedy = [];

% Draw source
if drawzb == 1
    % Physical topology
    figure(3);
    axis equal
    hold on;
    set(gca,'Box','on');
    plot(info(s, 2), info(s, 3),'k.', 'MarkerSize', 25);
    title('Broadcast on ZigBee physical network topology');
    xlabel('X');
    ylabel('Y');
    axis([0, maxX, 0, maxY]);
    set(gca, 'XTick', [0; maxX]);
    set(gca, 'YTick', [maxY]);
    % Logical topology: tree
    figure(5);
    axis equal
    hold on;
    set(gca,'Box','on');
    plot(tx(s), ty(s),'k.', 'MarkerSize', 25);
    title('Broadcast on ZigBee logical network topology');
    axis([0, tmaxX, 0, tmaxY]);
    set(gca, 'XTick', []);
    set(gca, 'YTick', []);
end

% Global greedy selection, no source needed
if approach == 4    
    % F = [];
    ggS = [];
    ggS = zeros(maxn, 3);
    % 1: index
    % 2: network ID
    % 3: degree
    ggS(:, 1)=[1:maxn]';
    for j = 1: size(ggS, 1)
        ggS(j, 2) = info(ggS(j, 1), 1);
    end
    ggC = [];
    ggC = [1:maxn]';
    while(length(ggC)>0)
        for j = 1: size(ggS, 1)
            u=ggS(j, 1);
            tn1 = [u, neighbor(u, 1:info(u, 5))]';
            ggS(j, 3) = maxNeighbor + 1 - length(intersect(tn1, ggC));
        end
        ggS = sortrows(ggS, [3, 2]);
        u = ggS(1, 1);  % the highest degree with the lowest network ID
        % info(u, 5) + 1 - ggS(1, 3)
        tn1 = [u, neighbor(u, 1:info(u, 5))]';
        ggS = ggS(2:size(ggS, 1), :);
        ggC = setdiff(ggC, tn1);
        if length(intersect(F, u)) > 0
            disp('********Global greedy: a forward node already chosen');
        end
        % F = union(F, u);  % sorted
        F = [F, u];  
        forward(u, 1) = 3;
    end
    if drawzb == 1
        for i = 1:length(F)
            if F(i) ~= s
                figure(3);
                plot(info(F(i), 2), info(F(i), 3), 'k.', 'MarkerSize', 25); % o', 'MarkerSize', 3, 'MarkerFaceColor', 'k', 'MarkerEdgeColor', 'k');
                figure(5);
                plot(tx(F(i)), ty(F(i)), 'k.', 'MarkerSize', 25); % o', 'MarkerSize', 3, 'MarkerFaceColor', 'k', 'MarkerEdgeColor', 'k');
            end
            for j = 1:info(F(i), 5)
                if forward(neighbor(F(i), j), 1) > 0
                    continue;
                end
                forward(neighbor(F(i), j), 1) = 1;
                figure(3);
                line([info(F(i), 2), info(neighbor(F(i), j), 2)], [info(F(i), 3), info(neighbor(F(i), j), 3)], 'Color', 'k');
                plot(info(neighbor(F(i), j), 2), info(neighbor(F(i), j), 3), 'ko', 'MarkerSize', 3);
                figure(5);
                line([tx(F(i)), tx(neighbor(F(i), j))], [ty(F(i)), ty(neighbor(F(i), j))], 'Color', 'k');
                plot(tx(neighbor(F(i), j)), ty(neighbor(F(i), j)), 'ko', 'MarkerSize', 3);
            end
        end
    end
    % Result
    numAlreadyforward = length(F);    
    numInitial = size(find(forward(:, 1)==0), 1);
    numNonforward = size(find(forward(:, 1)==1), 1);
    for i = 1:length(F)
        etimer(F(i)) = rand;
    end
    timeDelay = max(etimer);
    numAlreadyforward
    timeDelay
    return
end


% Other localized broadcast algorithms
forward(s, 1) = 2;     % source is the first to forward
etimer(s) = 1;
etimercount = etimercount + 1;
while(whilesign)
    toforward = find(etimer > 0);
    t1=length(toforward);
    if t1 <= 0
        break;
    end
    t2 = inf;
    for i0 = 1 : t1
        i = toforward(i0);
        if etimer(i) < t2
            t2 = etimer(i);
        end
    end
    % 0 < t2 < inf, t2 is the minimum positive time
    toforward = find(etimer==t2);  % toforward has at least 1 node
    etimer = etimer - t2;
    for i0 = 1 : length(toforward)
        i = toforward(i0);
        % Determine forwarding nodes F
        F = [];
        NF = [];
        if approach2 == 1
            % ZigBee: every tree neighbor will rebroadcast, but self-prune if all neighbors are covered
            F = tneighbor(i, 1 : info(i, 4) + 1);
            NF = setdiff(neighbor(i, 1 : info(i, 5)), F);
        elseif approach2 == 2
            % OSR: every neighbor will rebroadcast, but self-prune if all tree neighbors are covered
            F = neighbor(i, 1:info(i, 5));        
            NF = [];
        else    % Forward node selection
            % OOS, step 1, find S and C
            C = [];
            % C = TN(i)
            C = tneighbor(i, 1: info(i, 4) + 1);
            % C = TN(N(i))
            if info(i, 5) > 0
                S = neighbor(i, 1: info(i, 5));
                for j = 1 : info(i, 5)
                    if tneighbor(S(j), 1) > 0 | info(S(j), 4) > 0
                        C = union(C, tneighbor(S(j), 1:info(S(j), 4)+1));
                    end
                end
            else
                S = [];
            end
            % C is already sorted, remove first ids that < 0.
            t1=find(C < 0);
            t2=length(t1);
            if t2 > 0
                if t2 < length(C)
                    C = C(t2+1 : length(C));
                else
                    C = [];
                end
            end
            % C = TN(N(i)) - N(i)
            C = setdiff(C, [i , S]);
            if useu == 1
                % S -= TN(u), C -= TN2(u)
                u = forward(i, 2);
                if u > 0  % u is valid
                    tn1u = [u , tneighbor(u, 1: info(u, 4) + 1)];
                    S = setdiff(S, tn1u);
                    for j = 1: length(tn1u)
                        if tn1u(j) <= 0 | info(tn1u(j), 1) < 0
                            continue;
                        end
                        C = setdiff(C, [tn1u(j) , tneighbor(tn1u(j), 1: info(tn1u(j), 4) + 1)]);
                    end
                end
            end
            if useu == 1 & useFu == 1 & u > 0 & forward(u, 3) > 1   % F(u)-i is valid
                % S -= F(u), C -= TN(F(u))
                Fu = setdiff(forward(u, 4: 4+forward(u, 3)-1), i);
                S = setdiff(S, Fu);