Virtual-Sensing-Framework-VSF-/collection_tree.m at master · csarkar/Virtual-Sensing-Framework-VSF- · GitHub

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
%%
% author: Chayan Sarkar
% email: c.sarkar@tudelft.nl
%%
function parent = collection_tree(n, e_res, link)

    max_res = e_res(1);
    relay_cost = 2*max_res*ones(n,1);
    state = zeros(n,1);
    parent = -1*ones(n,1);


    parent(1) = 1;
    relay_cost(1) = 0;
    k = 1;
    cover = 1;

    while(cover < n)
        % update distance for the remaining nodes based on the newly select node
        for i=2:n
            if(state(i)==0 && link(i,k)>0 && i~=k)
                relay = 2*max_res - (e_res(i)+e_res(k));
                relay = relay + relay_cost(k);

                if(relay<relay_cost(i))
                  relay_cost(i) = relay;
                  parent(i) = k;
                end
            end
        end

        min_cost = 2*max_res;
        % find the node with minimum cost (among unmarked nodes)
        for i=2:n
            if(relay_cost(i)<min_cost && state(i)==0)
                min_cost = relay_cost(i);
                k = i;
            end
        end

        state(k) = 1;
        cover = cover+1;
    end


    pp = zeros(n-1,1);
    for i=2:n
        pp(i-1) = parent(i) - 1;
    end
    parent = pp;
end

%     max_res = e_res(1);
% relay_cost = 2*max_res*ones(n,1);
% state = zeros(n,1);
% parent = zeros(n,1);
%
%
% parent(1) = 1;
% relay_cost(1) = 0;
% k = 1;
% cover = 1;
%
% while(cover < n)
%     % update distance for the remaining nodes based on the newly select node
%     for i=2:n
%         if(state(i)==0 && link(i,k)>0 && i~=k)
%             relay = 2*max_res - (e_res(i)+e_res(k));
%             relay = relay + relay_cost(k);
%
%             if(relay<relay_cost(i))
%               relay_cost(i) = relay;
%               parent(i) = k;
%             end
%         end
%     end
%
%     min_cost = 2*max_res;
%     % find the node with minimum cost (among unmarked nodes)
%     for i=2:n
%         if(relay_cost(i)<min_cost && state(i)==0)
%             min_cost = relay_cost(i);
%             k = i;
%         end
%     end
%
%     state(k) = 1;
%     cover = cover+1;
%
% end
%
% pp = zeros(n-1,1);
% for i=1:n-1
%     pp(i) = parent(i+1) - 1;
% end
% parent = pp;