% % function [util,f,w,R] = minasym(C,D,R,pmax,rP,a,b,s,loss,htype,tip)%% given coordinate matrix C, trafix matrix D, Pmax, fading coefficient a<-2 and% CDMA coefficient b\in[0,1], find optimal routuing, scheduling and power% control, using heuristics%% Arguments: % C - coordinates of nodes% D - src-dst pairs (flows)% R{:} - routes between SD pairs (each line is a vector of nodes to go from S to D)% pmax - max power used% a - fading coefficient% b - CDMA interf. factor% s - (HEURISTIC) take this s as optimal% loss - node loss probability. see rndtopo2d.% htype - different heuristics. see in the code.% tip - yet another heuristis. see sched.m%% We tried several heuristics for solving the centralized optimisation problem, % but they don't improve much; therefore, one does not have to bother much playing with them.%% % Returns:% util - utility of the optimal schedule% f - rates of flows% w - weights of each of a slot in R% R - 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).%function [util,f,w,rates,err] = minasym(C,D,R,pmax,rP,a,b,s,loss,htype,tip)% set default heuristicsif nargin < 8	s = 0;endif nargin < 9	loss = 0;endif nargin < 10	htype = 'o';endif nargin < 11	tip = 'n';end%% Initialization:% - calculate fadings between nodes% - extract used links to an array L% - make routing matrix B (B*f <= x)H = makeH(C,[],a);n = length(C);% calculate average link length l based on links from R (i.e. links used)lavg=0; nl=0;% make a list of used links and there initial weights% (correspond to number of routes that passes through them).L = [];W = [];% construct a routing matrixB = [];for i=1:size(R,2)	route = R{i};	nl = nl + size(route,2)-1;	for j=1:(size(route,2)-1)		k=1;		% links are bi-directional		while k <= size(L,1) & (L(k,1) ~= route(j) | L(k,2) ~= route(j+1)) & ...							   (L(k,1) ~= route(j+1) | L(k,2) ~= route(j))			k=k+1;		end		if k > size(L,1)			k = size(L,1)+1;			L(k,1)=route(j);			L(k,2)=route(j+1);            W(k) = 1;        else            W(k) = W(k)+1;		end		B(k,i) = 1;		lavg = lavg + dist(route(j),route(j+1),C);	endendlavg = lavg/nl;l = size(L,1);W = W';% if s is given, we use given s% if not, we use heuristics to calculate optimal <s>if s < 0     optt = findoptt(L,C,pmax,rP,a);    else	optt = [];	for i=1:l		%Old		%t = dist(L(i,1),L(i,2),C) * s;				% In order to have a comparison with 802.11 like protocols, 		% we allow fix blocking region, and its radius is s (if positive)		optt = [optt, s * rP(L(i,1)).^(-1/a)];	end	end%% First, find the schedule (packing)% Next, find slot lengths (TDMA weights)% Since we use randomizes scheduling, we repeate several times and take the best value%err = 1;mutil = -Inf;optto = optt;norun = 5;if htype == 'r'   norun = 100;	norun = 5;endfor run=1:norun    % DEBUG    if htype == 'r'        optt = 2 * rand(size(optt)).*optto;    end    if htype == 'c'        W = ones(size(L,1),1);        end    rates = sched(L,C,optt,W,H,pmax,a,b,tip);    [util,f,w,lambda,e] = TDMAweights(B,rates);    if e <= 0        display('Error!');        % There was an error    	C'    	D'    	% save errr C netsize D R    else        if util > mutil            err = 0;            mutil = util;            mf = f;            mw = w;        end        % Use the lower line to include lagrange prices into schedule generation        % AFAIK this doesn't help much, but consumes time (time grows as CONST grows).        CONST = 10;        if htype == 'l'            W = ceil(CONST*(lambda - min(lambda))/max(lambda)) + 1;        end    endendif ~err	util = mutil;	f = mf;	w = mw;	% Calculate for loss	if loss > 0		tlen = 0;		for i = 1:length(f)			tlen = tlen + length(R{i})-1;		end		util = util + log(1-loss) * tlen;	endelse	util = -Inf;	f = [];	w = [];end