一种基于二分图匹配模型的多播寻呼机制

Multicast Paging Scheme Based on Bipartite Graph Matching Model

针对多播业务中,无线网络如何在带宽和时延受限的情况下,实现对于多个处于空闲状态的移动用户的跟踪定位问题,提出了一种有效的基于二分图匹配模型的多播寻呼机制。其主要思想是:首先通过利用信息论中熵的概念对移动用户的位置不确定性进行分析,为了减少位置更新开销,采用LZ78压缩算法实现位置更新和位置概率预测。然后多播寻呼系统为减少寻呼开销和时延,在每个寻呼周期内为所有移动用户分配的寻呼小区驻留概率之和最大,且满足带宽限制和用户公平性。针对该目标,基于二分图匹配的多播寻呼算法BMPS构建二分图模型,将位置概率转化为权值,通过动态修改权值,获取二分图最大权完美匹配,实现用户与寻呼小区之间的最优分配方案。仿真实验结果表明,基于二分图匹配的多播寻呼算法能够有效实现寻呼开销和时延的总体性能优化,且减少了用户冲突对寻呼性能影响。

Aiming at one of the most important problems in the multicast service of how the wireless network could track and locate the mobile users in idle state, under the tight bandwidth and delay constraints, an efficient multicast paging scheme was proposed based on bipartite graph matching model. By quantifying the location uncertainty of mobile users with entropy, the scheme adopted the LZ78 compression algorithm to design location update scheme and predict the location probability to reduce the cost of location update. With the purpose of optimal performance on both expected paging delay and paging cost, the multicast paging system needed to guarantee the maximum total probability that each user resided at the assigned paging area. Therefore, the bigraph-based multicast paging scheme （BMPS） firstly built the bipartite graph model of multicast paging problem, through converting the location probability into weight of the edge. BMPS decided the optimal allocation between the mobile users and location areas, which was mainly achieved by the maximum weight perfect matching in bipartite graph, with dynamically modified the weights. Simulation results show that BMPS yields a low paging delay as well as a low paging cost, and reduces the impact of user collision.