SETS:
 ! LINGO model for assigning frequency bands to links in a 
     radio communications network ;
 ! References:
   Li, M. and G. Zhu (2008), "Optimization Models of Multi-Channel Assignment
 in Multi-Radio Wireless Mesh Networks",
 Wireless Communications, Networking and Mobile Computing. 

   Shi, Y., Y. Hou, and H. Zhou(2009), 
  "Per-Node Base Optimal Power Control for Multi-Hop Cognitive Radio Networks",
  IEEE Transactions on Wireless Communications, vol. 8, no. 10, pp. 5290-5299.;

 ! Keywords: Communication, Radio network, Network, Channel assignment, 
             Wireless network, Cellular communication, Network;

 ! In a network, we want to choose
   a) which radio links to use, and
   b) which channel or band to use on each link so we
   can communicate without interference. If a lot of power is used
   to transmit from a particular source, it will cause a lot of
   interference on other nearby links that might wish to transmit
   on the same frequency band. So we want to choose a band for each
   chosen link that does not interfere with other nearby chosen links.
     Assumptions:
   There is a power loss exponent n and a threshold alpha,
   such that if 
       d(i,j) = distance from i to j, then a transmission
   at i will be successful received at j if the broadcast power p
   at i satisfies p >= (d(i,j)^n)*alpha.
   Similarly, a transmission at i on band k will cause interference at c,
   if c is receiving on band k from some other node t,
   and p > (d(i,c)^n)*beta.  Thus, a broadcast from i to j on band k
   will necessarily cause interference at c if
       c is trying to receive on the same band k, and
      (d(i,j)^n)*alpha > (d(i,c)^n)*beta.
   Thus, a broadcast from i to j must interfere with c using
   the same band if d(i,c)) < d(i,j*(alpha/beta)^(1/n).
   Shi, Hou, and Zhou suggest n = 4, alpha = 50, and beta = 50/16.
   Thus, a transmission from i to j will interfere with a
   transmission from elsewhere to c on the same band if d(i,c) < 2*d(i,j).

 Below, this apparently nonlinear integer program is formulated as
a linear integer program;

 NODE;  ! Set nodes in network;
 BAND;  ! Set of bands available for communication;
 LINK(NODE,NODE): d, QS, QI; ! Distances between nodes, transmit powers;
 NXB(NODE,BAND);     ! Set of feasible node band combinations;

! Set of possible link * band combinations. ;
 BXL( BAND, LINK) | @IN(NXB,&2,&1) #AND# @IN(NXB,&3,&1) #AND# &2 #NE# &3: 
      y;   ! b,i,j is possible if both nodes i and j can support band b;

! Decision Variables:
    y(b,i,j) = 1 if node i transmits to node j on band b, else 0,  ;
ENDSETS
DATA:
 NODE = N1..N10;  ! Set of nodes;
 BAND = B1..B10;  ! Set of bands;

! Which bands are available at which nodes;
 NXB = N1,B1 N1,B2 N1,B3 N1,B4 N1,B5 N1,B6 N1,B7 N1,B8 N1,B9 N1,B10  
       N2,B2 N2,B3 N2,B4 N2,B5 N2,B6 N2,B7 N2,B10
       N3,B1 N3,B3 N3,B4 N3,B5 N3,B6 N3,B7 N3,B8 N3,B9 N3,B10
       N4,B1 N4,B3 N4,B4 N4,B5 N4,B6 N4,B7 N4,B8 N4,B9 N4,B10
       N5,B1 N5,B2 N5,B5 N5,B6 N5,B7 N5,B8 N5,B9 
       N6,B1 N6,B2 N6,B4 N6,B8 
       N7,B1 N7,B2 N7,B3 N7,B4 N7,B5 N7,B6 N7,B7 N7,B8 N7,B9 N7,B10 
       N8,B1 N8,B3 N8,B4 N8,B5 N8,B7 N8,B8 N8,B9 
       N9,B1 N9,B3 N9,B5 N9,B7 
       N10,B1 N10,B2 N10,B3 N10,B4 N10,B6 N10,B7 N10,B8 N10,B9 N10,B10 ;

  
 ! Distances between nodes;      
d =  0	4.79	7.71	9.48	10.06	10.87	12.48	18.44	22.10	25.05
     4.79	0	7.22	9.49	13.95	14.86	14.64	20.15	24.91	27.73
     7.71	7.22	0	2.27	10.50	11.45	8.42	13.26	18.78	21.41
     9.48	9.49	2.27	0	10.00	10.90	6.68	11.08	16.87	19.41
     10.06	13.95	10.50	10.00	0	0.96	6.22	11.38	12.72	15.72
     10.87	14.86	11.45	10.90	0.96	0	6.72	11.53	12.31	15.30
     12.48	14.64	8.42	6.68	6.22	6.72	0	6.01	10.40	13.13
     18.44	20.15	13.26	11.08	11.38	11.53	6.01	0	6.98	8.82
     22.10	24.91	18.78	16.87	12.72	12.31	10.40	6.98	0	2.99
     25.05	27.73	21.41	19.41	15.72	15.30	13.13	8.82	2.99	0;



  N = 4;  ! Power dissipation exponent;
  alpha= 50;   ! Power successful communication threshold;
  beta = 3.125;! Power interference threshold;
 ! There may be an upper limit on the power;
  MAXPOW = 90000;
ENDDATA

 SUBMODEL CHUZLINKS:
! The y(b,i,j) variables are 0 or 1;
 @FOR( BXL(b,i,j) : @BIN( y(b,i,j)); );

! At most one band can be assigned to a link;
 @FOR( LINK(i,j) | i #NE# j:
  [JUST1] @SUM(BXL(b,i,j) : y(b,i,j)) <= 1;
     );

 ! The no-interference at j constraint;
 ! If node i transmits to node j using band b, then no node k # i 
    can also transmit on band b to some node h if that will
    cause interference at j, i.e., the power needed to
    transmit from k to h causes interference at j;
   @FOR( BXL(b,i,j):
      @FOR( NODE(k) |  k #NE# i:
      [INTFR] y(b,i,j) +
              @SUM( BXL( b,k,h) | QS(k,h) #GT# QI(k,j) : y(b,k,h)) <= 1;
          );
       );

 ! Zero out links that require more power than is allowed;
   @SUM( BXL(b,i,j) | QS(i,j) #GT# MAXPOW: y(b,i,j)) = 0;

! Various objectives and network connectivity constraints can be 
added to the above non-interference constraints. Here we simply... ;

! Maximize number of links on which we communicate;
  MAX = OBJ;
   OBJ= @SUM( BXL(b,i,j): y(b,i,j));

ENDSUBMODEL


CALC:

 ! Linearization exploits the fact that in the nonlinear program, an
optimal solution will transmit at the minimum power needed to achieve
successful transmission. So we compute that min power for each (i,j),
and remove it as a variable from the model, leaving it linear;
 @FOR( LINK(i,j):
 ! Compute minimum power at i needed to transmit to j;
   QS(i,j) = (d(i,j)^n)*alpha;
 ! Compute maximum power at i to not interfere at j on a given channel;
   QI(i,j) = (d(i,j)^n)*beta;
     );

   @SOLVE( CHUZLINKS); ! Solve the model;

   ! Write a little report;
   @WRITE(' A Little Report:', @NEWLINE(1));
   @WRITE('  Total links that can be operated= ', OBJ, @NEWLINE(1));
   @WRITE(@NEWLINE(1), '     Link:   Band used  Power',@NEWLINE(1));
   @FOR( BXL(b,i,j) | y(b,i,j) #GT# .5:
     @WRITE(' ',@FORMAT(i,'4.0f'),' ',@FORMAT(j,'4.0f'),'    ', 
      @FORMAT(b,'4.0f'),'    ',@FORMAT(QS(i,j),'9.2f'), @NEWLINE(1));
      );
ENDCALC