A study on cross layer optimizatio adapt given rate demands under dis power control in WMNS - Hoàng Trọng Minh

Kỹ thuật điện tử & Khoa học máy tính H.T. Minh, P. K. Toan, L. V. Ngoc, N. T. Tra, “ A study on cross layer control in IMNS.” 70 A STUDY ON CROSS LAYER OPTIMIZATION TO ADAPT GIVEN RATE DEMANDS UNDER DISCRETE POWER CONTROL IN WMNS HOÀNG TRỌNG MINH, PHẠM KHÁNH TOÀN, LÊ VĂN NGỌC, NGUYỄN THANH TRÀ Abstract: In multi-hop networks such as wireless mesh network, power control plays an important role in cross-layer Optimization problems due to its direct relationship with interference impacts. Power control strategies are potential approach to optimize network performance parameters in realistic environment. Unfortunately, these cross-layer optimal problems have to face with the hardest computation in finding a feasible solution; especially in case they are employed multiple practical constraints from physical layer. To overcome the challenge, this paper presents an investigation on jointly optimal joint routing, scheduling, channel assignment and power control in multi-radio multi-channel wireless mesh networks using a MAC layer based on Time Division Multiple Access (TDMA). In which, a discrete fashion of power control and physical interference model is considered to find out an optimal solution for given rate demands. The computation complexity is reduced by applying the column generation algorithm in the optimize problem. Keywords: Wireless mesh network, scheduling, Cross-layer optimization, Column generation algorithm, Discrete power control. 1. INTRODUCTION Wireless Mesh Networks (WMNs) have emerged recently as a new network architecture to extend the coverage and increase the capacity of wireless access networks. WMNs are being considered with several regular standards such as IEEE802.11, IEEE 802.15 and IEEE 802.16 [1]. In which, WMNs based IEEE 802.11 can be seen as the most popular technology to provide both reliable and high traffic path demand for last mile connection access by using a multi-radio multi-channel networking mode. Beside its advantages, WMNs have to face with many remained technical issue challenges related to network performance parameters under fairness criteria. To overcome these challenges, cross-layer optimization solved by the linear programming has been the greatest attracted by numerous studies because this approach is clarified with wide usage. However, finding out the feasible optimal solution is not easy task so that the complexity of the problem could be fall into NP-hard problem if there employed nonlinear factors or under practical assumes. Hence, studies in this field are continuing in progress. Power control is especially crucial and presented as a constraint in optimizing problem because it affects directly the interference in wireless networks. The continuous power control strategy is a nice approach to find the tradeoff between throughput and energy consumption [2]. To the best of our knowledge, most of works have modeled a power control scheme as a binary or continuous constraint variant to reduce the complexity of optimizing problem. However, wireless node may not have capability of controlling power continuously in practice, but rather support only a finite set of power levels [3]−[5]. Hence, our study focuses on the problem of joint routing, links scheduling, channel assignment and power control in Time Division Multiple Access (TDMA) based on Multi- Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 35, 02 - 2015 71 Channel Multi-Radio (MC-MR) WMNs, with the goal of determining the minimum length schedule time that satisfies a set of given traffic rate demand with discrete power control. To avoid NP-Hard problem of linear programming approach, the brand and bound methodology is applied. The rest of this paper is organized as follows. In next section, some main previous studies related to our study are briefly reviewed. In section 3, we formulate the optimization problem to find out the number of needed time slots to adapt a set of given demands. Section 4 shows the numerical results to verify our proposal. In last section, we conclude this study by summarizing our contributions and discussing directions for future work. 2. RELATED WORK Cross layer optimization problems in WMNs in order to optimize network performance objectives have received a lot of attention in the recent years. To increase the throughput provided to nodes, several studies have investigated TDMA scheduling techniques, i.e., to identify sets of links that can be simultaneously activated [6] [7]. In [6], it considers a binary interference model and fixed transmission power to propose an optimization framework for determining optimal routing and scheduling. The proposed solution approach in [8] is based on graph coloring and linear programming to produce a valid scheduling scheme for satisfying the maximum fraction of each demand. However, this proposal does not consider interference constraint. To satisfy a set of specified traffic demands, a joint scheduling, routing and power control strategy is proposed in[9] [10]. The authors in [9] developed a computational tool using column generation to maximize the minimum throughput among all flows while the objective in [10] is a minimum-length schedule. It was shown that power control can improve schedule length compared to a fixed transmit power. Scheduling optimization in WMNs with power control and rate adaptation is proposed in [11] using SINR (Signal to Interference and Noise Ratio) constraints in the well-known Physical Interference Model [11]. However, it considers a continuous power control to maximize activated simultaneous links which adapted the feasibility of demands. Because scheduling with power control using a SINR model is NP- hard [7] [13], several papers proposed heuristic algorithms to minimize the schedule length with and without power control [7] [14] [15]. In this study, the problem of joint routing, scheduling, channel assignment and power control is formulated to find out the optimal solution for a set of given rate demands under discrete power control constraint. Column generation processes dealing with the optimal problem are presented to avoid NP- Hard problem. Power control constraint in the problem is presented by a finite set of power levels to agree with practical condition. 3. PROBLEM FORMULATION 3.1. Network properties and Assumptions In this section, we provide the assumption underlying this study and introduce appropriate notations. Consider a multi-radio multi-channel wireless mesh network presents by a graph G(E,V) where V is a set of mesh nodes, and E is a set of links. Let’s denote the number of radios in node i as ri, i=1,2N and K orthogonal channels are available in the network without any inter-channel interference. A link is formed between two nodes if SINR level at receiver j exceeds threshold ( ) when a signal is transmitted by node i is given by: Kỹ thuật điện tử & Khoa học máy tính H.T. Minh, P. K. Toan, L. V. Ngoc, N. T. Tra, “ A study on cross layer control in IMNS.” 72 , . j ij j j l ill i j p G SINR p G     Where j p is the power emitted by node i , ijG is gain of radio channel and j is thermal noise. In multi-ratio multi-channel WMNs, end-to-end paths can be formulated in the multi-commodity flows form. In this problem, the constraints of channel, number of node’s radios and interference are presented as follows. , (i, j) ,stij ij s OC y w E t      (1) (ij) , ,stij i E s OC y r i V t        (2) 1, i,j , OC, tst stij jiy y V s       (3) (mn) /m , (i,j) , s OCst stij ij mj mn E i PG y PG y E                (4) Where (1) represent the maximum number of channel can active on link (i,j) at any time slot t, there are multiple wireless channels of operation and these channels are orthogonal to each other. The constraint (2) says that the number of radios in use does not exceed the radio equipment at each node. The constraint (3) is the half-duplex constraint operation of each node and (4) is the interference constraint with the use of Physical Interference Model. The notations using in the problem are presented in Table 1. Table 1. Index of key notations. ij csa Binary variable. It is 1 if link (i,j) active in channel s in configuration c C Set of configurations odD Number of packets to be sent from node o to node d E Set of network links od ijf Integer variable. It represents the number of packets of demand from node o to node d going through link (i,j) ij G Path gain of link (i,j)  Thermal noise P Power at each node s iP Power of node i active in channel s kP Power level k  SINR threshold ct Integer variable. It represents the number of timeslot where configuration c is actived OC Set of available orthogonal channels V Set of nodes ks ijv Binary variable. It is 1 if link (i,j) active and node i has power level k ir Number of radio interface in node i ij su Binary variable. It is 1 if link (i,j) active in channel s Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 35, 02 - 2015 73 st ijy Binary variable. It is 1 when link (i,j) active in channel s at time slot t ijw Number of orthogonal channel that link (i,j) can active in These constraints can lead to the NP-Hard problem when the size becomes larger causing the variables time-indexed. Without loss of generality, the given rate demand constraints are expressed in term of minimum number of needed time slots which directly depends on SINR at receiver and the network as a set of links that can be active together; thus a flow allocation problem changes to the configuration allocation problem to reduce computation complexity. To adapt a given rate demand of users, the feasibility of specific demand has to be determined. We want to know if a specific demand i.e. a set of pair nodes (source node and destination node) and the number of packet need to be sent which can be achieved in the network. In other words, the minimum number of used timeslots in optimal solution has to satisfy a specific demand. For more details, every transport session in TDMA WMNs is active in fixed time frame including T time slots. Thus, T value is the upper bound of number of available time slot in a time frame. Let T* be the optimal solution, the feasibility of demand is determined if only T*<T. The detail optimal solution of the optimization problem is described bellows. 3.2. Optimization Problem Assuming a set of activated simultaneous links is formed by all available orthogonal channels, we formulate the minimum number of used time slots by linear program as follows. min c c C t   (5) Subject to: ( , ) (j,i) if i=o if i=d 0 otherwise i N, (o,d) D od od od ij ji od i j E E P D f f D                (6) (o,d) D , (i,j) E P cs od ij c ij s OC c C a t f         (7) ( , ) (j,i) , i Vs sij ji i s OC i j E E a a r                (8) ( , ) (j,i) 1, i V, ,cs csij ji i j E E a a c C s OC            (9) ( , ) / PG (i,j) E, , cs cs ij ij mj mn m n E m i a PG a s OC c C                   (10) ,ct c C    (11) , (i,j) , (o,d) Dodij Pf E      (12) Kỹ thuật điện tử & Khoa học máy tính H.T. Minh, P. K. Toan, L. V. Ngoc, N. T. Tra, “ A study on cross layer control in IMNS.” 74 Where the objective function (5) asks for the minimization of the number of used time slot. Constraint (6) states flow conservation while constraint (7) ensures that each link is active in at least one slot for each packet to be sent. Three constraints (8) (9) (10) are the constraints of the number of radios at each node, half-duplex and interference like (2) (3) (4), respectively. The problem considered takes into account a set of activated links simultaneously, namely configuration. As the number of configuration is exponential, the number of column of the constraint matrix is exponential. It is hard to solve the problem by the simplex method because of the size of simplex tableau. To reduce the complexity in constructing the whole set of columns, we adopt a column generation based approach. The problem is decomposed into a master problem and a sub-problem. We solve the master problem with a small subset of columns, which serves as an initial basis. The sub-problem is then solved to check the optimality of the solution under the current master basis and to generate new columns for the master problem. This procedure repeats until the master problem contains all columns necessary to find the optimal solution of the original problem. Each column corresponds to one configuration. The master problem and sub- problem can be formulated as follow. Master problem Include objective function and constraint (5) (6) (7) (11) and (12) Sub-problem ( , ) min 1 sij ij i j E s OC q u            (13) Subject to: ( , ) (j,i) , i Vs sij ji i s OC i j E E u u r                (14) ( , ) (j,i) 1, i V, s sij ji i j E E u u s OC          (15) ( , ) / PG , (i,j) E, s sij ij mj mn m n E m i u PG u s OC                (16) {0,1}, (i,j) E siju    (17) The optimal solution of the optimization problem formulated above * min c c C T t    provides us the minimum number of needed time slots to satisfy a specific demand. Then, by comparing its value with the maximum number of available time slots in frame, we will know the demand is feasible or not and the optimal number of slots to satisfy it. 3.3. Optimization Problem with Discrete Power Levels Instead of keeping node’s power fixed and uniform, in the fact that each network node will have the ability to adjust its power as discrete power values. Our assumption is contracted to previous studies [10, 18, 19], where the power constraint can only receive one value of a finite set of power levels between minP and maxP . The power set that a node Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 35, 02 - 2015 75 can support is given by 0 1 2 1{ , , ... }K P P P P , where K is the number of power levels, 0 maxG  P and 1 max K P P . The power level k is calculated as follow 0 0 max 1 k Pk K     P P P .The joint routing, scheduling, channel assignment and discrete power control optimization problem can be formulated as follow. Master problem Include objective function and constraint (5) (6) (7) (11) and (12) Sub-problem Include objective function and constraint (13) (14) (15) (17), replacing (16) by (18) and adding (19) (20) (21), we have ( , ) / P G (i,j) E, s s s i ij ij m mj m n E m i u P G s OC                 (18) ij ( , ) 1 P , i V, s OC K s k ks i i j E k v        P (19) ij 1 , (i,j) E, s OC K ks s ij k v u       (20) {0,1}, (i,j) E, s OC, k=1...Kksijv       (21) In the next step, we need to linearize the nonlinear constraints (4) (10) (16) (18) to linear constraints. For example, we will linearize constraint (16), the other nonlinear constraints can be linearized in the similar way. The linear formulation of the (16) is ( , ) / PG M(1-u ) (i,j) E, s s ij ij mj mn m n E m i PG u s OC                  (22) Where M is a constant factor, max max 2 N M G P         . 4. NUMERICAL RESULTS AND DISCUSSIONS In this section, we use numerical results to verify the effectiveness of our work. We consider a (3 X 4) regular grid topology with 12 nodes that deployed in a 1000 square meter area, as shown in Figure 1. Figure 1. A grid network scenario. Kỹ thuật điện tử & Khoa học máy tính H.T. Minh, P. K. Toan, L. V. Ngoc, N. T. Tra, “ A study on cross layer control in IMNS.” 76 The main assumed parameters are presented in Table 2. The column generation algorithm is implemented and tested using AMPL/CPLEX [16], [17]. We start our numerical analysis considering a network without channel assignment (a node employed one channel and one network interface card) in three cases: fixed power, continuous and discrete power control. We assume there are 15 source-destination maximum pairs can be activated simultaneously as show in Table 3 below. Table 2. Assumed parameters Dimension of a network 3 4 Distance between two nodes 100 m Available transmission rate 1 packet/ time slot SINR threshold 2 Thermal noise 610 ( )mW  Path loss exponent 3  Maximum transmission power max 15 ( )P mW Needed packets for each demand 10 packets Table 3.The demanded connection set. Pair 1 1-12 Pair 2 9-4 Pair 3 5-3 Pair 4 8-10 Pair 5 11-2 Pair 6 3-10 Pair 7 4-6 Pair 8 6-12 Pair 9 7-1 Pair 10 10-4 Pair 11 12-5 Pair 12 9-7 Pair 13 1-11 Pair 14 5-8 Pair 15 8-1 With the networks has employed 1 NIC and single channel, the minimum number of needed time slots for every control strategy is presented in Figure 2. The result shows that when the number of demand pairs is increased then the difference of the minimum number time slots among them is growth. When the network has a small number of demand pairs, the impact of power control strategies on the network performance is not clear distinction. The time slots used for discrete power control case is always smaller than continuous power control case in all number of demand pairs. To evaluate our problem in multi-hop networks with multi-radio multi-channel, we consider a network that contains every node having 2 channels and 2 NICs. A power set in every node has 3 and 5 power levels to compare with fixed power case and continuous case to provide a practical engineering insight on WMN. We consider the reasonable power levels to comfort with regular packet size of services such as TCP, UDP and data packets. The demand pairs are selected to illustrate the wide range of carrier traffic in the wireless mesh network. The running time of discrete power control case increases nearly linear curve as the increment of demand pairs. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 35, 02 - 2015 77 Figure 2. Power control strategies in single radio single channel network. Figure 3. Power control strategies in multi- radio multi- channel network. The results in Figure 3 shows that when the number of channel increases and the number of source – destination pair increases lead to the needed minimum time slots in discrete power control case get closer to continuous power control case. The number of minimum time slots in the discrete power control case is always over fixed power case. The optimal minimum time slots of the two power levels is slightly different but the running time of 5 power levels case is longer 15% than that of 3 power levels case in the same simulated conditions. Moreover, the number of power levels is slight impacted to the minimum time slot when the network has a large demand number. Kỹ thuật điện tử & Khoa học máy tính H.T. Minh, P. K. Toan, L. V. Ngoc, N. T. Tra, “ A study on cross layer control in IMNS.” 78 5. CONCLUSION Power control in discrete fashion is crucial strategy to deploy wireless mesh network in real environment. This paper proposed the cross-layer optimization problem that considers discrete power control constraint with realistic interference model. By introducing the column generation algorithm, the complexity of optimization problem is reduced and the simulation results are presented to examine our proposed problem in the example scenarios. Since the needed minimum time slot in continuous power control is often smaller than discrete power control, we investigate that the difference comes to slightly when the number of channels and network interface cards increases. Hence, the discrete power control strategy can be applied in multi-channel multi-radio high density WMNs. On our next works, a practical routing protocol based on the approach will be implemented to get closer to practical wireless mesh networks applications. REFERENCES [1]. I. F. Akyildiz, X. Wang, and W. Wang, “Wireless Mesh Networks: A Survey,” Computer Networks Journal (Elsevier), Vol. 47, no. 4 (2005), pp. 445-487. [2]. A. Ouni, H. Rivano, F. Valois, C. Rosenberg, "Energy and Throughput Optimization of Wireless Mesh Networks with Continuous Power Control," Wireless Communications, on IEEE Transactions, no.99 (2014), pp.1-14. [3]. Nikos et all, “Joint Multi-Cost Routing and Power Control in Wireless Ad Hoc Networks,” Springer Science Business Media, LLC 2010. [4]. T. N. Nagabhushan, S.P.S. Prakash, and K. Krinkin, “Battery Draining Rate Aware Optimized Link State Routing in Wireless,” Conference of Open Innovations Association (FRUCT), 2013, pp. 122-131. [5]. J. Luo, A. Iyer, and C. Rosenberg, “Throughput-lifetime trade-offs in multi-hop wireless networks under an SINR-based interference model,” IEEE Transactions onMobile Computing, Vol.10, no. 3 (2011) , pp. 419–433. [6]. C. Molle, F. Peix, and H. Rivano, “An optimization framework for the joint routing and scheduling in wireless mesh networks,” The 19th Annual IEEE International Symposium on Indoor and Mobile Radio Communications (PIMRC), France, September 2008. [7]. K. Bastian, V. Markus, and W. Dorothea, “Energy efficient scheduling with power control for wireless networks,” In Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks, France, June 2010. [8]. Dutta, Partha et al, “Joint Routing and Scheduling in Multi-hop Wireless Networks with Directional Antennas,” IEEE, 2012, pp. 1–5. [9]. J. Luo, C. Rosenberg, and A. Girard, “Engineering wireless mesh networks: Joint scheduling, routing, power control and rate adaptation,” IEEE/ACM Transactions on Networking, Vol.8, Issue 5 (2010) pp. 1387–1400. [10]. S. Kompella et all, “On optimal SINR-based scheduling in multi-hop wireless networks,” IEEE/ACM Transactions on Networking, 2010 pp.1713 – 1724. [11]. A. Capone et all, “Routing, scheduling and channel assignment in Wireless Mesh Networks: Optimization models and algorithms,” Ad Hoc Networks (8), 2010, pp. 545-563. Nghiên cứu khoa học công nghệ Tạp chí Nghiên cứu KH&CN quân sự, Số 35, 02 - 2015 79 [12]. P. Gupta, P. Kumar, “The capacity of wireless networks,” IEEE Transactions on Information Theory, Vol.46 (2), 2000, pp. 388–404. [13]. O. Goussevskaia, Y. A. Oswald, and R. Wattenhofer, “Complexity in geometric SINR,” In The 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing, USA, 2007, pp. 100–109. [14]. Gang Lu and B. Krishnamachari, “Energy efficient joint scheduling and power control for wireless sensor networks,” In Second Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, USA, 2005, pp. 362–373. [15]. B. Sansò, S. Boiardi, and A. Capone, “Energy-Aware Planning and Management of Wireless Mesh Networks,” In IEEE Globecom, Atlanta (USA), 2012. [16]. R. Fourer, D.M. Gay, B.W. Kernighan, “AMPL: A Modeling Language forMathematical Programming,” second edition, 2003. [17]. ILOG CPLEX 11.0 Users Manual. . NGHIÊN CỨU TỐI ƯU XUYÊN LỚP ĐÁP ỨNG CÁC YÊU CẦU TỐC ĐỘ ĐẦU VÀO DƯỚI ĐIỀU KIỆN ĐIỀU KHIỂN CÔNG SUẤT RỜI RẠC CHO CÁC MẠNG HÌNH LƯỚI KHÔNG DÂY WMNS Tóm tắt: Trong các mạng không dây đa bước như mạng hình lưới không dây, vấn đề điều khiển công suất đóng vai trò rất quan trọng đối với mục tiêu tối ưu hiệu năng mạng do có mối quan hệ trực tiếp tới hiện tượng nhiễu. Các chiến lược điều khiển công suất là tiếp cận tiềm năng để tối ưu hiệu năng mạng trong các điều kiện thực của môi trường. Tuy nhiên, các bài toán tối ưu xuyên lớp này phải đối mặt với các tính toán phức tạp nhất khi tìm kiếm lời giải khả thi; đặc biệt là trong đó có các đa ràng buộc thực tiễn ở lớp Vật lý. Để vượt qua thách thức, bài báo này trình bày một nghiên cứu đề xuất bài toán tối ưu xuyên lớp giữa định tuyến, gán kênh và điều khiển công suất cho mạng hình lưới không dây đa kênh đa vô tuyến hoạt động theo cơ chế đa truy nhập phân chia theo thời gian TDMA. Cơ chế điều khiển công suất rời rạc và mô hình nhiễu vật lý được giả thiết nhằm thể thể hiện các điều kiện thực để tìm kiếm lời giải tối ưu cho các cặp yêu cầu kết nối. Trở ngại về độ phức tạp tính toán của bài toán tối ưu được giải quyết thông qua thuật toán tạo cột và xác minh bằng mô phỏng số. Từ khóa: Mạng hình lưới không dây, Lập lịch, Tối ưu xuyên lớp,Thuật toán tạo cột, Điều khiển công suất rời rạc. Nhận bài ngày 12 tháng 08 năm 2014 Hoàn thiện ngày 15 tháng 01 năm 2015 Chấp nhận đăng ngày 10 tháng 02 năm 2015 Địa chỉ: Khoa viễn thông 1, Học viện công nghệ bưu chính viễn thông; điện thoại: 0913.259.259; Email: hoangtrongminh@ptit.edu.vn.