A Quasi-Solution State Evolution Algorithm for Channel Assignment Problems in Cellular Networks(Special Section on Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
For efficient use of limited electromagnetic wave resource, the assignment of communication channels to call requests is very important in a cellular network. This task has been formulated as an NP-hard combinatorial optimization problem named the channel assignment problem (CAP). Given a cellular network and a set of call requests, CAP requires to find a channel assignment to the call requests such that three types of interference constraints between channels are not only satisfied, but also the number of channels (channel span) is minimized. This paper presents an iterative search approximation algorithm for CAP, called the Quasi-solution state evolution algorithm for CAP (QCAP). To solve hard CAP instances in reasonable time, QCAP evolutes quasi-solution states where a subset of call requests are assigned channels and no more request can be satisfied without violating the constraint. QCAP is composed of three stages. The first stage computes the lower bound on the channel span for a given instance. After the second stage greedily generates an initial quasi-solution state, the third stage evolutes them for a feasible channel assignment by iteratively generating best neighborhoods, with help of the dynamic state jump and the gradual span expansion for global convergence. The performance of QCAP is evaluated through solving benchmark instances in literature, where QCAP always finds the optimum or near-optimum solution in very short time. Our simulation results confirm the extensive search capability and the efficiency of QCAP.
- 社団法人電子情報通信学会の論文
- 2002-05-01
著者
-
Nakanishi Toru
Department Of Communication Network Engineering Faculty Of Engineering Okayama University
-
Higashino Teruo
Department Of Informatics And Mathematical Science Osaka University
-
Higashino Teruo
The Department Of Informatics And Mathematical Science Graduate School Of Engineering Science Osaka
-
Nakanishi T
Department Of Communication Network Engineering Okayama University
-
Funabiki N
Graduate School Of Natural Science And Technology Okayama University
-
Yokohira Tokumi
The Authors Are With The Department Of Communication Network Engineering Okayama University
-
FUNABIKI Nobuo
The authors are with the Department of Communication Network Engineering, Okayama University
-
NAKANISHI Toru
The authors are with the Department of Communication Network Engineering, Okayama University
-
TAJIMA Shigeto
The authors are with the Department of Informatics and Mathematical Science, Osaka University
-
HIGASHINO Teruo
The authors are with the Department of Informatics and Mathematical Science, Osaka University
-
Tajima Shigeto
Graduate School Of Engineering Science Osaka University
関連論文
- A WDS Clustering Algorithm for Wireless Mesh Networks
- An Anonymous Bidding Protocol without Any Reliable Center (特集 情報セキュリティの理論と応用)
- A Linkable Group Signature and Its Application to Secret Voting
- An Optical-Drop Wavelength Assignment Algorithm for Efficient Wavelength Reuse under Heterogeneous Traffic in WDM Ring Networks(Discrete Mathematics and Its Applications)
- A Minimum Dead Space Algorithm for Generalized Isochronous Channel Reuse Problems in DQDB Networks(Network)
- P2PMM_router : A Two-Stage Heuristic Algorithm to Peer-to-Peer Multicast Routing Problems in Multihome Networks(Discrete Mathematics and Its Applications)
- A Quasi-Solution State Evolution Algorithm for Channel Assignment Problems in Cellular Networks(Special Section on Discrete Mathematics and Its Applications)
- Time-Action Alternating Model for Timed Processes and Its Symbolic Verification of Bisimulation
- A Proposal of Optimal Path Selection Algorithm for Static and Mobile Multicast Routing Problems
- Deriving Concurrent Synchronous EFSMs from Protocol Specifications in LOTOS (Special Section on Selected Papers from the 11th Workshop on Circuits and Systems in Karuizawa)
- A Method to Convert Concurrent EFSMs with Multi-Rendezvous into Synchronous Sequential Circuit(Special Section on Concurrent Systems Technology)
- Execution Time Analysis for Binary Code Executed on a Pipelined Processor Using Parametric Model Checking
- Relaxation of Coefficient Sensitiveness to Performance for Neural Networks Using Neuron Filter through Total Coloring Problems
- A Proposal of Neuron Filter: A Constraint Resolution Scheme of Neural Networks for Combinatorial Optimization Problems
- A Digital Neural Network for Multilayer Channel Routing with Crosstalk Minimization
- A Massive Digital Neural Network for Total Coloring Problems
- A Gradual Neural Network Approach for Time Slot Assignment in TDM Multicast Switching Systems
- Comparisons of Energy-Descent Optimization Algorithms for Maximum Clique Problems (Special Section on Discrete Mathematics and Its Applications)
- A Minimal-State Processing Search Algorithm for Graph Coloring Problems
- An Unlinkable Divisible Electronic Cash Using Secure Proxy Computation for DL One-way Function (特集:新たな脅威に立ち向かうコンピュータセキュリティ技術)
- BS-5-29 An Idea of Linux Implementation of Fixed Backoff-time Switching Method for Wireless Mesh Networks(BS-5. Network and Service Design, Control and Management)
- A Fixed Backoff-Time Switching Method for CSMA/CA Protocol in Wireless Mesh Networks