find_landmark.m

来自「best routing protocol」· M 代码 · 共 39 行

function [lm_idx,rest_idx] = find_landmark(D, k, algorithm)
% D is the pairwise distance/bandwidth
% k is the number of landmarks
% if algorithm is 'rand', use random landmarks, otherwise use kmeans
% use kmeans algorithm to find centroid, then find the closest one
N = length(D);
if nargin==3 & strcmp(algorithm,'rand')
    tmp = randperm(N); 
    lm_idx = tmp(1:k); % choose random L nodes as landmarks
    rest_idx = tmp(k+1:N);  % the rest of them are orinary hosts
    return
end
if ~strcmp(algorithm,'kmeans')
    error('unknown algorithm for landmark selection')
end
finished = 0;
while finished~=1
    try
        [k_idx, cen] = kmeans(D, k);
        finished = 1;
    catch
        fprintf('kmeans failed. let us do it again\n');
        finished = 0;
    end
end
    
dist = euclidean_distance(D, cen);
[stuff lm_idx]=min(dist);
lm_idx = sort(lm_idx);
N = length(D);
tmp_idx = [lm_idx N+1];
rest_idx = 1:N-k;
start = tmp_idx(1);
for i=2:k+1
    len = tmp_idx(i)-tmp_idx(i-1)-1;
    rest_idx(start: start+len-1)=tmp_idx(i-1)+1:tmp_idx(i)-1;
    start = start+ len;
end