WLAN Resource Management using Distributed Constraint Optimization

PI: Anita Raja

Collaborators: Dr. Linda Xie, ECE, UNCC; Professor Ivan Howitt, UNCC.

RA: Shanjun Cheng

Sponsor: NSF

This research investigates cooperative resource management in WLAN (wireless local area networks) /WPAN (wireless personal area networks) interference environments. The objective of this research is to manage shared system resources fairly among multiple WLANs to optimize the overall performance. Expected results from the project will have a significant impact on next generation WLAN network management based on employing algorithms of agent interaction and coordination to facilitate resource management, predictive models for parameter estimation, and dynamic load balancing algorithms.

Approach

A multi-agent system-based approach is used to achieve information sharing and  decision distribution among multiple WLANs in a distributed manner.

                       Figure 1: WLAN as a Multiagent system [Xie07b]                                Figure 2: Block diagram of physical envoronment prediction and agent operations [Xie07b]

Architecture

This research maps the WLAN resource management problem as a distributed constraint optimization problem (DCOP) as shown in Figure 2. It studies the effectiveness of DCOP algorithms to find the optimal resource assignment through communications between distributed agents.

Mapping the WLAN to a DCOP

A simple WLAN scenario(M:Mobile Station, A: Access Point

• A={A1,...,An}:set of agents,each Acess Point is assigned an agent
• X={X1,...,Xm}:set of variables, each Access Point has a variable Xi for Mobile Station
• D={d1,...,dm}:set of domains of variables
• R={r1,...,rp}:set of relations,ri is a utility function

We extend Petcu's DPOP algorithm, a distributed constraint optimization algorithm to solve the mapped WLAN resource allocation problem. DPOP is a Utility Propagation algorithm based on dynamic programming , it requires a linear number of messages.

Motivating Example

          Figure 3: 8-APs WLAN Scenario [Cheng09]                         Figure 4: Pseudo-tree for the WLAN scenario in Figure 3 [Cheng09]

                          Figure 5: Perturbation at AP1[Cheng09]                                       Figure 6: Repaired Pseudo-tree where edge AP1-AP4 is removed [Cheng09]

Solution

We developed a multi-agent approach for decentralized load balancing in WLANs. This approach uses DLB-SDPOP [Cheng09], a constraint optimization algorithm to determine the optimal allocation of MSs under each AP. DLB-SDPOP dynamically repairs the affected nodes in the original pseudo-tree retaining the topology and states of unaffected nodes when inconsistency is detected.

Experiments

                     Figure 7: Simulation Scenario [Cheng09]

                Figure 8: DLB-SDPOP Compared with other DCOP algorithms [Cheng10]

Co-PIs: Anita Raja (MAS focus), Professor Linda Xie (ECE), Professor Ivan Howitt (ECE)
RAs: Shanjun Cheng, James Rozi
　

Links:

• This project is supported by NSF. The program webpage can be found here.
• The presentation of this project can be found here.

Publications:

• [Cheng10] Shanjun Cheng, Anita Raja, Linda Xie, Ivan Howitt, "DLB-SDPOP: A Multiagent Pseudo-tree Repair Algorithm for Load Balancing in WLANs" In Proceedings of    2010 IEEE/ WIC/ ACM International Conference on Intelligent Agent Technology (IAT-2010) , pp 311-318, Toronto, Canada (Acceptance Rate 18.8%, Received Best Paper Award). 
• [Cheng09] Shanjun Cheng, Anita Raja, Linda Xie, Ivan Howitt "A Distributed Constraint Optimization Algorithm for Dynamic Load Balancing in WLANs". In Proceedings of Eleventh International Workshop on Distributed Constraint Reasoning to be held in conjunction with IJCAI 2009, pp 31-45, Pasadena CA.
• [Xie07a] Jiang Xie, Ivan Howitt, and Anita Raja, "Cognitive Radio Resource Management Using Multi-Agent Systems," Proceedings of First IEEE Workshop on Cognitive Radio Networks (CRN 2007), in conjunction with IEEE Consumer Communications and Networking Conference (CCNC 2007), 2007.
• [Xie07b] Jiang Xie, Ivan Howitt, and Anita Raja, "Framework for Decentralized Wireless LAN Resource Management" To appear in Emerging Wireless LANs, Wireless PANs, and Wireless MANs, Edited by Dr. Xiao and Dr. Pan, to be published by Wiley , 2007.c
• Acknowledgement: This material is based upon work supported by the National Science Foundation under Grant Nos. IIS: 1018067 and CNS: 0626980. Any opinions, findings and conclusions or recomendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation (NSF).