How to generate realistic wireless network topology?

Recently, I’m working on a scheduling algorithm on wireless sensor network with Matlab. But when it comes to the very first topology generation, it becomes complex than I thought.

Here is what I have done:

• random generate nodes on planar with uniform distribution, remove nodes that’s too near to existing nodes.
• generate mesh grid topology with a coverage range, nodes within the range can establish connection.
• set the geometry middle point as root, generate tree topology by Dijkstra’s algorithm.

And here is preliminary result and codes.

The result is too simple and uncontrollable now. Most importantly the generate tree seems imbalanced, i.e the degree/number of children vary much, which seems not expected. Obviously, I need more constraint to make it more realistic.

I don’t need to carefully place the nodes to achieve minimum power consumption, nor to design channel model or structure of nodes, but some baselines like best coverage, less nodes, less interference, less traffic load(in bit*meter) is expected.

I survey and find tool like NPART https://www.informatik.hu-berlin.de/de/Members/milic/NPART, and someone says maybe NS3 can help. But I have limited time on it, anyway it’s just part of my research.

Could anybody give me some easy-implement hints or useful tools?

%== code follows ==

% X = randn(50,2);
% randn - normal  vs rand - uniform
% guassian distribution
% Y = reshape(1:100,50,2);
% plotmatrix(X)
% scatter(X(:,1),X(:,2));

% figure;
% Y = rand(50,2)*50;
% scatter(Y(:,1),Y(:,2));

% non-overlap distance > 5

distinct_BOUND = 5;
Z = zeros(50,2);
T = rand(1,2)*50;
Z(1,:) = T;
for i = 2:50
    T = rand(1,2)*50;
    for j = 1:i-1        
        while pdist([T;Z(j,:)],'euclidean') < distinct_BOUND
            T = rand(1,2)*50;
        end
    end
    Z(i,:) = T;
end
% 
% figure;
% scatter(Z(:,1),Z(:,2));

% == find root ==
m = mean(Z);
d = pdist([m;Z(1,:)],'euclidean');
r = Z(1,:);
root = 1;
for i = 2:50
    if pdist([m;Z(i,:)],'euclidean') < d
        d= pdist([m;Z(i,:)],'euclidean');
        r = Z(i,:);
        root = i;
    end
end

% result Node 44

Weight = zeros(50,50);
for i = 1:50
    for j = 1:50
        Weight(i,j) = pdist([Z(j,:) ; Z(i,:)],'euclidean');
    end
end

% set a upper bound for distance, no connection for distance exceed it.

% == remove 'weak' link to generate mesh
coverage_range = 10; % the shorter, the deeper tree
for i = 1:50
    for j = 1:50
        if  Weight(i,j) > coverage_range
            Weight(i,j) = 0;    % cancel 'too long' distance
        end
    end
end

G = Weight;
G = sparse(G);
% root = 41;
[dist, path, pred] = graphshortestpath(G, root);
% Dijkstra,Time complexity is O(log(N)*E)

NUM_link = length(cell2mat(path));

G_adj = zeros(50,50);
for i = 1:50
    for j = 1:50
        if G(i,j)~=0
            G_adj(i,j) = 1;
        end
    end
end

gplot(G_adj,Z);  % gplot(G,Z) for the same

depth_MAX = 10;
path_mat = zeros(50, depth_MAX);
for i = 1:50
    t = cell2mat(path(i));
    t(depth_MAX)=0;
    path_mat(i,:) = t;
end

G_tree = zeros(50,50);
for i = 1:50
    for j = 1:nnz(path_mat(i,:))-1
        s = path_mat(i,j);
        t = path_mat(i,j+1);
        G_tree(s,t) = 1;
    end
end

   gplot(G_tree,Z);

[Sneha Kolapalli]

how can we label the nodes in this question??

Answer 1

[Walter Roberson]

My thought is that your removal of nodes that are "too near to existing nodes" is the essential problem in your algorithm. Each time you place a node, you sweep out a circle of radius distinct_bound around it that no other node can be present in. The closet packing you can theoretically get in such a system is a mess of equilateral triangles in which the sides of the larger triangle are at least sqrt(3) * distinct_bounds . But you prune out links when the distance is greater than 10 (which happens to be 2 * distinct_bounds), so you are selecting for links that happen to be between sqrt(3) and 2, out of a possible range of 0 to sqrt(2) * 50 . You are thus selecting a sparse subset, so it is not surprising that you end up with something fairly thin.

Your third diagram is known as a spanning tree. It is not uncommon for them to be branch-y like that. They are useful for making sure that messages do not get indefinitely circulated, that any given message is always being sent "closer" to the destination. However, they are not the proper protocol for maximum effectiveness in local data sharing. Consider for example the upper right in your second diagram, the nearly equilateral triangle there: in the diagram below, two of the edges has been removed, so if communications had to take place between two of the nodes, the communication could have to go through three hops.

Spanning tree also does not allow link aggregation: if any one link is limited in speed but you can transmit on more than one link at the same time, then you may be able to get the data to the destination faster by sending portions through multiple routes. Consider if A has 100 units to send, and

A speed 50 to B, A speed 50 to C, B speed 100 to D, C speed 100 to D

then in Spanning Tree, time step 0 to 1 A would transmit 50 to B, in time step 1 to 1.5 B would transit the 50 to D and then notify A it was ready for more. Time step 1.5 to 2.5, A would transmit the second 50 to B, time step 2.5 to 3.0 B would transit it to D, and would notify A it was ready for more. Elapsed time 3.0

But if transmission to multiple links is possible, time step 0 to 1, A would transmit 50 to B and simultaneously 50 to C, and time step 1 to 1.5, B would transmit 50 to D and simultaneously C would transmit 50 to D. Elapsed time 1.5. At worst, if D has a total simultaneously receive capacity of 100 per time step, B and C might have to take 1 time step at speed 50, total 100 between them, for an elapsed time of 2.0 -- which beats the 3.0 needed if you follow spanning tree links only.

There are other protocols which can take these link capacity matters into account. Some of those protocols might use Spanning Tree as one step to determine whether the network has become partitioned by one of the key links dropping out (a distinct possibility in wireless networks that might be moving or where obstacles might be moving.) Spanning tree is useful -- but it is not the most efficient, especially if you have "nearby" nodes communicating for various reasons. With Spanning Tree, two nodes that are directly connected can end up on opposite sides of the tree -- and even if that for some reason works out for "bandwidth" purposes, it introduces latency as messages are relayed.

[Yu Jianyuan]

Sir: Sincerely appreciate for your patient rely, even for details in codes and outputs. Here I add more explanation for my setting to make my question more clear.

- set distinct bound is essential, although the proper value of the distinct bound matters. We place nodes/sensors here to collect data, in certain area, one node is enough to cover the area, more nodes in such area would increase cost and bring trouble, it would increase the possibility of interference in wireless network due to the radio communication character.

- the coverage range matter, as preliminary result show, too short coverage range makes weak connection and thin tree(I refine my code later to avoid the case for unconnected graph), too long coverage range makes strong connection and star like tree but also means too strong interference for communication.

- non-spanning tree indeed helps, actually ieee802.15.4 prefer DODAG(https://tools.ietf.org/html/rfc6550) method for non spanning tree to make the connection more flexible. However, it involved in complex routing issue here I don’t expected. Here is my refined code s and outputs.

%====== code =====
function [] = my_scatter(N, L, coverage_range)

% ref input 50,50,20
% non-overlap distance > 5
% coverage_range ; % the shorter, the deeper tree

% == random coordination == 
distinct_BOUND = 5;
Z = zeros(N,2);
T = rand(1,2)*L;
Z(1,:) = T;

for i = 2:N
    u = true;
    v = false;               
    while u || v        
        T = rand(1,2)*L;        
        % u is true if new added node is too far to all node
        u = true;
        for j = 1:i-1
            if pdist([T;Z(j,:)],'euclidean') < coverage_range
                u = false;
            end
        end       
        % v is true if if new added node is too near to one node
        v = false;
        for j = 1:i-1
            if pdist([T;Z(j,:)],'euclidean') < distinct_BOUND
                v = true;
            end
        end       
    end    
    Z(i,:) = T;
end

% == figure raw nodes ==
figure;
scatter(Z(:,1),Z(:,2));
s = sprintf('N-%d,L-%d, cr-%d nodes', N, L, coverage_range);
title(s); 
s1 = sprintf('N%d_L%d_cr-%d_nodes.png', N, L, coverage_range);
print(gcf,'-dpng',s1) ;

% == find root ==
m = mean(Z);
d = pdist([m;Z(1,:)],'euclidean');
r = Z(1,:);
root = 1;
for i = 2:N
    if pdist([m;Z(i,:)],'euclidean') < d
        d= pdist([m;Z(i,:)],'euclidean');
        r = Z(i,:);
        root = i;
    end
end

Weight = zeros(N,N);
for i = 1:N
    for j = 1:N
        Weight(i,j) = pdist([Z(j,:) ; Z(i,:)],'euclidean');
    end
end

% set a upper bound for distance, no connection for distance exceed it.
% == remove 'weak' link to generate mesh
for i = 1:N
    for j = 1:N
        if  Weight(i,j) > coverage_range
            Weight(i,j) = 0;    % cancel 'too long' distance
        end
    end
end

% == shortest path alg ==
G = Weight;
G = sparse(G);
% root = 41;
[dist, path, pred] = graphshortestpath(G, root);
% Dijkstra,Time complexity is O(log(N)*E)

NUM_link = length(cell2mat(path));

G_adj = zeros(N,N);
for i = 1:N
    for j = 1:N
        if G(i,j)~=0
            G_adj(i,j) = 1;
        end
    end
end

% == figure mesh ==
figure; 
gplot(G_adj,Z);
s = sprintf('N-%d,L-%d, cr-%d mesh', N, L, coverage_range);
title(s);
s2 = sprintf('N%d_L%d_cr-%d_mesh.png', N, L, coverage_range);
print(gcf,'-dpng',s2) ;

depth_MAX = 20;
path_mat = zeros(N, depth_MAX);

depth = zeros(N,1); 
for i = 1:N
    t = cell2mat(path(i));
    depth(i) = length(t);
    t(depth_MAX)=0;
    path_mat(i,:) = t;
end
Depth = max(depth); % in case multi output
Depth = Depth(1);

G_tree = zeros(N,N);
for i = 1:N
    for j = 1:nnz(path_mat(i,:))-1
        s = path_mat(i,j);
        t = path_mat(i,j+1);
        G_tree(s,t) = 1;
    end
end

degree = zeros(1,N);
for i = 1:N
    degree(i) = nnz( G_tree(i,:) );
end
degree_avg = mean(degree); 

% == figure tree ==
figure; 
gplot(G_tree,Z);
s = sprintf('N-%d,L-%d, cr-%d tree', N, L, coverage_range);
title(s);
s3 = sprintf('N%d_L%d_cr-%d_tree.png', N, L, coverage_range);
print(gcf,'-dpng',s3) ;

end

output

-- lower coverage range leads in less links and thin tree

-- lower node density(i.e nodes in large space)

%