sched.m

这是一个超宽带的源码

%
% function rates=sched(L,C,optt,W,H,pmax,a,b,tip)
%
% Calculate the optimal schedule using heuristics.
%
% Arguments:
% C - coordinates fo nodes
% optt(i) - distance around node i where there must be no active nodes at the same time
% W - (integer) weights of links denoting how many times should each link be in the schedule
% H - fading matrix
% tip - one type of heuristic (see below)
% ...
%
% Returns:
% rates - an array of rows, each representing a slot. If R(i,j) > 0 it means node i 
%         is allocated full power in slot j and achieves rate R(i,j).
%
%
% Generates a schedule by a greedy heuristics. Starts a new slot <current>
% and tries to schedule as many links as possible in this slot, giving
% priority to those that has been scheduled less before (used(<j>)).
% Continues adding new slots until all links have been scheduled at least
% once.
%
%

function rates=sched(L,C,optt,W,H,pmax,a,b,tip)


if nargin<9
	tip = 'n';
end


n = size(L,1);
rates = [];
% total rate assigned to each link in assigned schedules, assuming all slots have equal times
used = zeros(n,1);


% generate a random permutation as an index array to ensure enough randomness
% find first link that is not scheduled enough, that is, the one whose number of
% schedules is smaller than its weight.

rndp = randperm(n);
i = 1;
while i <= n & used(rndp(i)) >= W(rndp(i))
    i = i+1;
end

if i <= n
    changed = 1;
else
    changed = 0;
end



while changed
    
    
	% start a new slot and add link <i> which is 
	% the first link that has not been scheduled before
	% <current> is the cshed for the current slot
	current = zeros(n,1);
	current(rndp(i)) = 1;
	    
	added = 1;
	while added
		% try to add more links in the same slot and repeat it 
		% while there are new links successfully added.
		added = 0;
		jmax = -Inf;
		j = 1;


		% find link <j> with minimal used(j) s.t. it can be added in the existing slot
		while j <= n

			k=1;
			allowed = 1;

			while k <= n & allowed
				% heuristic: we want to increase blocking distance if a node has already been scheduled
            % if k is added, it is "better" than j, so no need to multiple optt(j) by factor
				% PARAMETER (also factor does not need to be linear)
            % TO BE RECONSIDERED W.R.T WEIGHTS!
            
            % const is another heuristic param that is not very important
            const = 1.1;
            factor = max(const*(used(rndp(j))-used(rndp(k))) + 1,1);
				range = factor*optt(rndp(k));
					
				%tested exp heuristic (not any better nor worse)
				%range = optt(rndp(k))^factor;
                
				% if <k> is already scheduled in the current slot and <j> "interferes" with <k>
				% (see upper heuristic) then <j> is not scheduled.
                
				if current(rndp(k)) == 1 & (dist(L(rndp(k),2),L(rndp(j),1),C) < range |...
													 dist(L(rndp(j),2),L(rndp(k),1),C) < optt(rndp(j)) |...
													 L(rndp(k),1) == L(rndp(j),1) | L(rndp(k),1) == L(rndp(j),2) |...
													 L(rndp(k),2) == L(rndp(j),1) | L(rndp(k),2) == L(rndp(j),2))
					allowed = 0;
				end

				k = k+1;
			end

			% check if the newly found <j> has smaller utilisation used(j) than the one found by now
			% if true, add this link since it is estimated to have lower throughput
			if allowed & (W(rndp(j))-used(rndp(j))) > jmax
				jmax = (W(rndp(j))-used(rndp(j)));
				maxj = j;
				added = 1;
			end
			
			j = j+1;
		end

		if added
			current(rndp(maxj)) = 1;
		end
	end




	option = zeros(n,1);

	if tip == 'h'

		% ADDITIONAL HEURISTIC - done when the initial schedule is already done
		% if <k> is already scheduled in the current slot and <j> does not "interferes" with 
		% the receive of <k>, but <k> does possibly interfere with the receiver of <j>
		% try scheduling <j> anyway, but don't count it. This way <j> will improve its rate by eps
		% without bothering other nodes.

		added = 1;
		while added
			% try to add more links in the same slot and repeat it 
			% while there are new links successfully added.
			added = 0;
			jmax = -Inf;
			j = 1;


			% find link <j> with minimal used(j) s.t. it can be added in the existing slot
			while j <= n

				k=1;
				allowed = 1;

				while k <= n & allowed
   	         const = 1.1;
      	      factor = max(const*(used(rndp(j))-used(rndp(k))) + 1,1);
					range = factor*optt(rndp(k));
					
					% additional heuristic:
					% if <k> is already scheduled in the current slot and <j> does not "interferes" with 
					% the receive of <k>, but <k> does possibly interfere with the receiver of <j>
					% try scheduling <j> anyway, but don't count it. This way <j> will improve its rate by eps
					% without bothering other nodes.
                
					if current(rndp(k)) == 1 & (dist(L(rndp(k),2),L(rndp(j),1),C) < range |...
													 L(rndp(k),1) == L(rndp(j),1) | L(rndp(k),1) == L(rndp(j),2) |...
													 L(rndp(k),2) == L(rndp(j),1) | L(rndp(k),2) == L(rndp(j),2))
						allowed = 0;
					end

					k = k+1;
				end

				% check if the newly found <j> has smaller utilisation used(j) than the one found by now
				% if true, add this link since it is estimated to have lower throughput
				if allowed & (W(rndp(j))-used(rndp(j))) > jmax
					jmax = (W(rndp(j))-used(rndp(j)));
					maxj = j;
					added = 1;
				end
			
				j = j+1;
			end

			if added 
				current(rndp(maxj)) = 1;
				option(rndp(maxj)) = 1;
			else
				added = 0;
			end
		end
	end




    
	% Once all links in the slot have been scheduled, calculate achieved rates
	% for all scheduled links	
	ra = zeros(n,1);
	for j=1:n
		if current(j) > 0
			I = 0;
			for k=1:n
				if k~=j & current(k) > 0
					I = I+H(L(k,1),L(j,2));
				end
			end
			I = 1+b*pmax*I;
            
			snr = pmax*H(L(j,1),L(j,2))/I;
			% rate is a lin f. of SNR, but we don't care about the coefficient
			ra(j) = snr;
			if ~option(rndp(j))
				used(j) = used(j) + 1;
			end
		end
	end

    
	%used = used + ra;
	rates = [rates,ra];

	rndp = randperm(n);
	i = 1;
	while i <= n & used(rndp(i)) >= W(rndp(i))
		i = i+1;
	end

	if i <= n
		changed = 1;
	else 
		changed = 0;
	end
    
end