کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
431587 688591 2011 16 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
G-PaMeLA: A divide-and-conquer approach for joint channel assignment and routing in multi-radio multi-channel wireless mesh networks
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
G-PaMeLA: A divide-and-conquer approach for joint channel assignment and routing in multi-radio multi-channel wireless mesh networks
چکیده انگلیسی

The performance of Multi-Radio Multi-Channel Wireless Mesh Networks (MRMC-WMNs) based on the IEEE 802.11 technology depends significantly on how the channels are assigned to the radios and how traffic is routed between the access points and the gateways. In this paper we propose an algorithmic approach to this problem, for which, as far as we know, no optimal polynomial time solutions have been put forward in the literature. The core of our scheme consists of a sequential divide-and-conquer technique which divides the overall Joint Channel Assignment and Routing (JCAR) problem into a number of local optimization sub-problems that are executed sequentially. We propose a generalized scheme called Generalized Partitioned Mesh network traffic and interference aware channeL Assignment (G-PaMeLA), where the number of sub-problems is equal to the maximum number of hops to the gateway, and a customized version which takes advantage of the knowledge of the topology. In both cases each sub-problem is formulated as an Integer Linear Programming (ILP) optimization problem. An optimal solution for each sub-problem can be found by using a branch-and-cut method. The final solution is obtained after a post-processing phase, which improves network connectivity. The divide-and-conquer technique significantly reduces the execution time and makes our solution feasible for an operational WMN. With the help of a detailed packet level simulation, the G-PaMeLA technique is compared with several state-of-the-art JCAR algorithms. Our results highlight that G-PaMeLA performs much better than the others in terms of packet loss rate, collision probability and fairness among traffic flows.

Research highlights
► Local optimization sub-problems reduce the execution time in JCAR problems.
► A reduced execution time means obtain solutions applicable to operational WMNs.
► Knowledge about topology speeds up JCAR problems in WMNs.
► A physical interference model improves accuracy in JCAR solutions.
► In JCAR problems fairness among flows is an important factor.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Parallel and Distributed Computing - Volume 71, Issue 3, March 2011, Pages 381–396
نویسندگان
, , , , ,