Efficient Stable Matching Algorithms for Multi-sided Ubiquitous Networking Services

Stable matching is to best and stably “match” betweenuser preferences and service quality,subject to the resource constraints. This fundamental issue has been widely studied and applied in economic and social systems last decades. Nowadays, multi-sided ubiquitous networking services (MUNS) are such kinds of systems and playing significant roles in our daily life. A MUNS system normally involves multiple agents of client/server or user/server/data source (sensors) connected through networks such as wireless sensor/mesh networks, cellular networks and Internet of Things etc. where the system capability and network bandwidths are the resource constraints. For those systems, it is critical to have thebest matchbetween user preferences and service quality so as the users can bebestserved and the system resources bebestutilized. However, to the best of our knowledge, this fundamental issue has been ignored in the research of MUNS.In this proposal, we will study the fundamental problems for MUNS and investigate related algorithms. We will start with research of two-sided optimal (popular) matching for data sources allocations to user-preferred multi-jobs and then switch to stable matching for both three-sided agents i.e., users/servers/data sources, and groups of such agents. For easy illustration of the algorithms, we will use multi-camera network as the reference system for MUNS. Specific tasks include: 1) Investigate the problem ofmulti-job popular matching with non-unitary resource allocationand propose novel Popular Matching for multi-Request assignments (PMR) algorithm to maximize the matching popularity; 2) Seek the stable matching for three-sided cyclic preferred agents.If the agent number on each side larger than or equal to 6, then the stable matching may NOT exist.To attack this problem, we will propose a novel3-sided Matching with Size and Cyclic preference (3MSC)model and related algorithms. The algorithms will find a smart searching route for stable matching even theagent number has no limitedand theresourceis allocatednon-unitarily;3) Design the efficientgroup matching algorithms.We will propose novel scalable group matching algorithms for both two- and three-sided agents. The algorithms will enhance the scalability of solutions of PMR and 3MSC from 1-1 (one service to one user) to 1-nkwherenkis the number of users in groupkwith similar preferences. To maximize the on-line service flow throughput, we will seek the optimal relay servers. It is conjectured that this problem is NP-complete and its approximation algorithm will be investigated; 4) Implement above algorithms into a multi-camera networking system to demonstrate the feasibility and efficiency of all the algorithms for general MUNS systems.Completion of this project will help Hong Kong to an irreplaceable position in the novel concept, fundamental research, algorithm designs, system development and knowledge transfer based on novel theoretical results and technology developed. With the expected outcomes, the project will benefit HK with 1) Novel theory concepts, algorithms, and systems to deal with the related fundamental issues in wide spectrum; 2) High quality publications and 3) Intellectual Property generated from the project and technology transfer will potentially promote HK's scholarship and industries to upgrade their level worldwide.