%% 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';endn = size(L,1);rates = [];% total rate assigned to each link in assigned schedules, assuming all slots have equal timesused = 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;endif i <= n    changed = 1;else    changed = 0;endwhile 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