Optimal broadcast scheduling in packet radio networks using mean field annealing

被引:98
作者
Wang, GS [1 ]
Ansari, N [1 ]
机构
[1] NEW JERSEY INST TECHNOL,DEPT ELECT & COMP ENGN,CTR COMMUN & SIGNAL PROC,NEWARK,NJ 07102
关键词
D O I
10.1109/49.552074
中图分类号
TM [电工技术]; TN [电子技术、通信技术];
学科分类号
0808 ; 0809 ;
摘要
Packet radio (PR) is a technology that applies the packet switching technique to the broadcast radio environment. In a PR network, a single high-speed wideband channel is shared by all PR stations, When a time-division multi-access protocol is used, the access to the channel by stations' transmissions must be properly. scheduled in both time and space domains in order to avoid collisions or interferences, It is proven in this paper that such a scheduling problem is NP-complete. Therefore, an efficient polynomial algorithm rarely exists, and a mean field annealing-based algorithm is proposed to schedule the stations' transmissions in a frame consisting of certain number of time slots, Numerical examples and comparisons with some existing scheduling algorithms have shown that the proposed scheme can find near-optimal solutions with reasonable computational complexity. Both time delay and channel utilization are calculated based on the found schedules.
引用
收藏
页码:250 / 260
页数:11
相关论文
共 12 条
[1]  
Aarts E., 1989, Wiley-Interscience Series in Discrete Mathematics and Optimization
[2]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[3]  
Bertsekas D., 1987, DATA NETWORKS
[4]   SCHEDULING BROADCASTS IN MULTIHOP RADIO NETWORKS [J].
EPHREMIDES, A ;
TRUONG, TV .
IEEE TRANSACTIONS ON COMMUNICATIONS, 1990, 38 (04) :456-460
[5]  
HOPFIELD JJ, 1982, P NAT ACAD SCI, P2541
[6]   OPTIMIZATION BY SIMULATED ANNEALING [J].
KIRKPATRICK, S ;
GELATT, CD ;
VECCHI, MP .
SCIENCE, 1983, 220 (4598) :671-680
[7]   SPATIAL REUSE IN MULTIHOP PACKET RADIO NETWORKS [J].
KLEINROCK, L ;
SILVESTER, J .
PROCEEDINGS OF THE IEEE, 1987, 75 (01) :156-167
[8]   ISSUES IN PACKET RADIO NETWORK DESIGN [J].
LEINER, BM ;
NIELSON, DL ;
TOBAGI, FA .
PROCEEDINGS OF THE IEEE, 1987, 75 (01) :6-20
[9]   EQUATION OF STATE CALCULATIONS BY FAST COMPUTING MACHINES [J].
METROPOLIS, N ;
ROSENBLUTH, AW ;
ROSENBLUTH, MN ;
TELLER, AH ;
TELLER, E .
JOURNAL OF CHEMICAL PHYSICS, 1953, 21 (06) :1087-1092
[10]  
Peterson C., 1989, International Journal of Neural Systems, V1, P3, DOI 10.1142/S0129065789000414