通信技术
移动电话网络的优化设计
柳俊峰1
(陕西理工学院数学系陕西汉中723000)
数事执术与高用
摘要：本文针对移动电话网络的设计问题移动电语网络如何事局，对移动通讯公同的成本具有重大影响.用0-1整数规划方法建立移动电话网络设计模型,采用计算机算法中的分支一定界法解决此问题，在ingo中编程求出蜂寓与环路之间的最优连接方索。
关键调：0-1整数规对分支定界lingo
中图分类号：TN9 1、引言
文献标识码：A
文章编号：1007-9416(2011)08-0028-02
CAP：表示环路的总宽带；
MTSO：表示表示移动电话交换局节点：
上图是一个典型的移动电话网络结构图，每个基本地理区域称为-个蜂离(cel1)，将由一个成为中继站的收发器提供服务，从一个移动电话拨出的电话呼叫将首先通过这些中继站，每个中维继站都通过绳线或微波连接到一个中间结点(枢纽hub).其中有一个枢纽将对此网络进行控制，此枢纽即为MTSO(移动电话交换局)如果发生故障，则此环路可以自动重建连接，因此不需要对其全部替换.蜂宽c和环路之间的连接数目称为蜂宽c的多径数.从蜂窝c发出的通信量TRAF_c可以平均分配到蜂窝与环路之间的各个连接上，每个连接分配的通信量为TRAF_C/ CNTC_C.此通信量将通过环路传输到交换局，在交换局中将把各个呼叫转接到另一个蜂窝或移动电话与固定电话之间按的接口结点，由于交换局具有普通枢组的所有功能，因此中继站也可以直接连接到交换局，
蜂窝2 两个连接
蜂窝1 两个连接中继站
枢纽2
枢纽3
中继站
极组4
环路
极组1
交换局
现考虑一个有10个蜂窝和5个结点组成的环路的网络，系统中的通信是完全的数字化，通信宽带可以表示为宽带为64kbps的双向回路数目.环路的总宽带为CAP=48.交换局为结点5.目标是找到蜂窝与环路之间的连接方案，以最小化总连接费用，同时仍然能够满足通话量限制，并满足连接数要求.每个蜂宽的通话量，要求连接数以及每个连接的成本如下表。"
蜂窝枢纽1 枢组2 E 4 极纽5
15 18 7 1 10
22
通话量连接数2
12 9 11 8 5 14 12 2
2、模型建立
3 12 6 7 15 15 20 2
4 17 5 9 18 24 12
首先相关符号说明如下： 28
存数据
T5 8 22 21 19 6 15 3
16 7 25 15 9 17 25
17 19 25 21
22 15
20 9 15 18 25
2
9
10
12
125 22
24
14 16 20 8 2
13 4 1 22 2
CELLS：表示需要进行连接的蜂窝集合： NODES=HUBSUMTSO：表示结点集合： COST：表示将蜂窝c连接到结点n的成本；
comecr。：表示二值变量，当且仅当蜂离c连接到结点n时取1，否则取0
根据本题最小化总连接费用的要求以及能够满足通话量限制和连接数的限制备件，可以建立如下0一1整数规划模型，
minZ
cOST,.·connect.
cCELsNOOes sy.
eonmecf, = CNNT, acNooG
ETRAF
-connecf, ≤ 2- CAP
eCLsNOsCNCT
TRAF
·connect., ≤2·CAP(c ± 0)
sCNCT, 1
Ve e CELLS, n e NODES: connect, (b,1)
(1)(2)(3)(4)
约束(1)保证每个蜂窝的连接数都测足要求，约束(2)保证环路的通信量不超过上限，所有来源的所有通话要求都经过交换局，然后沿着环路的某个方向继续传输，由于环路的每条边的通信容量上限均为CAP，因此环路的总通信量不能超过2·CAP.也应该注意如果蜂窝与交换局直接相连，则它们之间的通信不需要进入环路.为
信需要，当每个蜂窝c都有一条连接直接连接到交换局上时，环路中的通信容量最小，此时环路带宽需要能够满足剩余的通信量，因
此可以得到最小通信容量约束条件(3) 3、模型求解
对于整数规划间题，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合.对于变量数较小的情况，这种方法是可行的，也是有效的.但是对于大型间题，可行的整数组合是很大的，这种方法是不可行的，一般仅检查可行的整数组合的一部分，就能定出最优的整数解.分支一定界法是求解此问题最常用的方法之一
分支定界法计算过程：
(1)去掉整数要求，求出问题的最小值，如所求解为整数解，计算停止，如果不是整数，则设定x=，转到(2)分支
(2)以原问题或上一子间题为基础，分别增加两个约束，构成两个子间题：3,≤[6],构成第一个子间题.$≥[]+1,构成第二个子间题.其中，6]表示)的整数部分的值，
(3)分支原则；无效解不分支，整数解不分支，虽不是整数解，但
..下转第30页