# Integer-linear-programing optimization in scalable video multicast with adaptive modulation and coding in wireless networks.

1. IntroductionRapid advancement in mobile wideband wireless network (i.e., 4G and 5G) supports real time services such as IPTV and live video streaming. Nevertheless, efficient resource allocation is required to satisfy delay requirements and to overcome the bandwidth shortage due to the increased number of users. Because of the sharing nature of the wireless medium, the wireless multicast has attracted much attention when multiple users want to receive the same video service at the same time [1].

Multicast service in wireless heterogeneous networks can adaptively choose a certain modulation and coding scheme (MCS) [2] based on the channel status and the hardware capability of the receivers. For the nonscalable coding (or called a single-layer coding) the multicast data rate and video quality are determined by the user who experiences the worst channel status [1, 3].

To alleviate the video performance degradation caused by the user who has the worst channel status, scalable video coding (SVC) [4] with adaptive modulation and coding (AMC) provides an excellent solution. In SVC, a video stream is divided into multiple layers. SVC encodes video with the nested dependency: the base layer encodes the basic video quality and higher layers, called the enhancement layers, refine the visual quality from the base layer with smaller quantization granularities. To enhance the overall performance of wireless multicast video streaming, we assign a low MCS to base layer and high MCSs to enhancement layers, so that the users in bad channel conditions receive fewer enhancement layers and obtain basic video quality, while the users in good channel conditions receive more enhancement layers and obtain better video quality.

A key issue arising under this setting is how each layer selects its MCS under the constraint of available radio resources for multicast services. A lot of research has studied the resource allocation problem in wireless multicast streaming video services [5-10]. In particular, [8,10] are most closely related to our research work, which provides solutions in both the single channel and slot TDMA-based networks. Reference [8] proposed an algorithm that guarantees full coverage which provides all destinations with at least a base layer to accommodate them. It allocates other MCSs to the enhancement layers with a heuristic algorithm to maximize the sum of utilities of all the receivers. It assumed that the size of each video layer is the same and the utility function of a user is simply a log function of the received data. The size of each layer is usually different, such that SVC supports various video qualities. The video quality experienced by a user is peak signal-to-noise ratio (PSNR) not a simple log function, so PSNR should be used in the resource allocation.

Reference [10] formulated a model that provides different size for each layer to support various video qualities. It used PSNR as a utility function to reflect the video quality experienced by a user and utilized dynamic programming for optimal network design. While the PSNR depends on the number of received packets in a layer, it increases only when all the packets in a layer are received fully. This PSNR model cannot be applied to other encoding methods of which PSNR increases with respect to the received packets. Hence, the PSNR which is the function of the received packets has to be derived. To search for an optimal solution easily, it assumes that the packet size and the slot size are fixed. However, if data rate is varied, the fixed-size slot cannot be utilized fully. Thus, if the slot size is determined based on each MCS, more video data can be transmitted without idle time in a slot.

To overcome these problems, we analyze PSNR models of various SVC encoding methods and choose a utility function to accommodate all the PSNR models. We also formulate a model which varies the slot size based on each MCS and utilize integer linear programming (ILP) to obtain the optimal solution.

The rest of the paper is organized as follows. The background and system architecture are discussed in Section 2. In Section 3, we present the system model and utility formulation. The problem formulation is described in Section 4. Section 5 explains ILP modeling and Section 6 shows the numerical results. Finally, Section 7 concludes the paper.

2. Background

2.1. Scalable Video Coding. Scalable video coding compresses a raw video sequence into a base layer and one or multiple enhancement layers. The base layer provides video data whose resolution is low, while the higher layers refine the video generated by the lower layer. SVC can provide adaptive video quality in wireless networks, but its performance is poor in terms of video quality compared to single-layer coding. Recently, SVC has improved its coding efficiency. For example, the newly established MPEG-4 SVC provides equal visual quality comparable with H.264/AVC (single-layer coding) but with at most 10% higher bit rate.

The quality of video can be measured using PSNR, which is a nondecreasing function of the received video data [11-15]. The PSNR function has different shapes according to encoding schemes, and it can be classified into four groups as illustrated in Figure 1 [11-15]. From Figure 1, we can observe that the functions of Figures 1(a) and 1(d) are represented as piecewise linear functions directly. However, Figures 1(b) and 1(c) show nonlinear functions, and so we approximate them to piecewise linear functions in the next section.

2.2. Mobile Wireless Systems. In infrastructure-based wireless networks, we consider the video multicast. A video server is equipped in the layered video codec to encode the video into multiple layers as illustrated in Figure 2. The video server then streams the video from all layers to APs (or base stations). The number and the size of the layers corresponding to each video frame are delivered to APs for every video frame period. The connection speed between the video server and the APs (or base stations) is high and reliable. Video stream is usually transmitted at a constant bit rate and an AP or base station forwards the packets delivered by video server to users for fragmentation. So, the packet size is fixed and is transmitted in a wireless channel.

Scheduling (resource allocation) in a wireless network MAC is done once for every scheduling frame period whose length is identical to the length of the video frame in our system. A scheduling frame consists of multiple time slots. The size of a time slot is the minimum time required to transmit a packet with a MCS. It means that the maximum number of available slot sizes is equal to the number of MCSs.

We consider the heterogeneous wireless networks, and so the users who experience relatively bad channel status can select a relatively high rate that leads to the considerable packet loss. In our system, each user measures its SNR and finds which MCS indicates the maximum data rate that satisfies target BER (bit error ratio) to decode the received data. An AP or base station assigns the radio resource and MCSs to layers to maximize the sum of utilities of all users to find the optimal solution.

3. System Model and Utility Formulation

We consider the one-hop broadcasting in wireless networks for the problem formulation. There are J users, and F is the size of a scheduling frame period, which is equal to that of video frame period. We assume a set of possible MCSs M = {1, ..., M} (e.g., MCS m = 1 indicates QPSK-1/2 and others). High MCS m means a high data rate. If a user can decode the data provided by MCS m by satisfying a target BER, it can also decode the data that is less than MCS m. [M.sub.j] [member of] M is the maximum MCS, which can be received by user j based on the channel status. User j transfers its MCS [M.sub.j] [member of] m to its AP (base station). [t.sub.m] is the time slot size given by MCS m. We consider a single multicast session which has L layers. Each layer is divided into many slices, which is also split into the packets of fixed-size. [N.sub.l] is the number of packets of layer l.

Now, we explain a utility function and the related variables. As aforementioned, the satisfaction of the users is proportional to the quality of multimedia defined as PSNR, which is a function of the received throughput. We assume that there is no packet loss in the wireless channel. That is, user j can decode a packet if it is transmitted by MCS m' [less than or equal to] [M.sub.j]. As illustrated in Figure 1, the PSNR function has four types. First, we are focusing on the second scheme of Figure 1(c) because the other schemes can be easily explained using this.

As we can see in Figure 1(c), it is nonlinear function and ILP cannot be formulated. In this paper, we approximate it with piecewise linear function as illustrated in Figure 3. We can see that there is relatively large difference between the original PSNR and the approximated one with a few packet losses. However, in case of more packet loss, it shows little difference. In fact, the packet loss which shows relatively large difference is quite less among all the packets and so it is not critical. Although this is incomplete, it can guarantee higher total utility than those of the existing methods [8-10] because the existing methods just consider a utility model that increases only when a user receives a layer completely. This approximation also can be formulated by ILP modeling. Figure 3 shows that the function has zero utility until it reaches the threshold, indicating the number of packets [[delta].sub.l] which does not increase the video quality in a layer. Let [[alpha].sub.l,m] be the number of received packets which have zero utilities in layer l. The utility function increases linearly when the packets in a layer l are received from the threshold St to the number of packets [N.sub.l] of layer l'. Let [[beta].sub.l,m] be the number of received packets which increases the utility linearly. Denote [[gamma].sub.l,m] as the indicator function that is 1 if layer l is transmitted by [for all]m' [less than or equal to] m and 0 otherwise:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (1)

Denote [z.sub.l,m] as the indicator function that is 1 if all the received packets [[beta].sub.l,m] are modulated by [for all]m' [less than or equal to] m and 0 otherwise:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (2)

Here, we set that [z.sub.l,0] = 0 because [[beta].sub.l,0] = 0. Hence, with these indicator variables, we utilize the approximated PSNR model as the utility function of the user j given as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (3)

with the constraints of layer transmission:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (4)

where [[phi].sub.l] is the PSNR weight of the packets which increases

the utility of layer l linearly. [[phi].sub.l] is the PSNR weight of the complete reception of layer l. [r.sub.m][t.sub.m][[phi].sub.l][[beta].sub.l,m] in (3) means the approximated PSNR to [[beta].sub.l,m] in layer l. [[phi].sub.l]([z.sub.l,m] - [z.sub.l,m-1]) in (3) means the approximated PSNR by the complete reception of layer l. That is, if the last packet of layer l is transmitted by MCS m', ([z.sub.l,m] - [z.sub.l,m-1]) has 1 only if m = m', otherwise zero.

Three other methods of the utility function can be easily derived as follows. If we set [[delta].sub.l] = 0, the first scheme can be formulated. If we set [[delta].sub.l] = 0 and [[phi].sub.l] = 0, the third scheme can be formulated. If we set [[phi].sub.l] = [N.sub.l], the final scheme can be formulated.

4. Problem Formulation

In this paper, we formulate an ILP problem to assign modulation and coding scheme for each layer in terms of the sum of utilities under any given resource constraints. That is, we have to find out

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

in order to

Maximize [summation over ([for all]j)] [U.sub.j] (6)

following the total time constraints:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (7)

and layer transmission constraints (1), (2), and (4). Since this formulation does not consider the nested dependency of SVC, it cannot solve the optimal solution yet. We present three lemmas to get an optimal solution.

Lemma 1. In the optimal solution of the multicast resource allocation problem in wireless networks with the encoding methods [11], if the last packet of layer l - 1 is transmitted using modulation m', the packets that have zero utility in layer l use m, and then it must be m [greater than or equal to] nm'. That is, the following condition should be satisfied:

0 [less than or equal to] [[alpha].sub.l,m] [less than or equal to] [[delta].sub.l][z.sub.l-1,m] (8)

with constraint of [z.sub.l,m], (2).

Proof. We assume that two layers l and l' use modulations m and m', respectively. If l > l' and m < m', one can improve the utility by swapping m and m' because the utility of packets of layer l using m is less than and equal to the utility of layer l using m.

Lemma 2. In the optimal solution of the multicast resource allocation problem in wireless networks with the encoding methods [11], if the last packet which has zero utility in layer l is transmitted using modulation m', the packets that have nonzero utilities in layer l use m; then, it must be m [greater than or equal to] m'. That is, the following condition should be satisfied:

0 [less than or equal to] [[beta].sub.l,m] [less than or equal to] ([N.sub.l] - [[delta].sub.l]) [y.sub.l,m] (9)

with constraint of [y.sub.l,m], (1).

Proof. We assume that packets which have zero utilities and packets which increase the utility linearly of layer l use m and m', respectively: [[alpha].sub.l,m] and [[beta].sub.l,m]. If m < m', one can improve the utility by swapping m and m because the utility of [[beta].sub.l,m] is less than and equal to the utility of [[beta].sub.l,m'].

Lemmas 1 and 2 mean that a MCS can be assigned sequentially in the ascending order. We define full coverage property which guarantees that all the users receive the minimum video quality in Lemma 3.

Lemma 3. Let [J.sub.m] be the set of users that can receive MCS m. To accommodate all users, the base layer should be transmitted by the MCS [m.sub.base] = max{m: [J.sub.m] = J}:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (10)

Proof. The proof follows from the fact (1) that all users have to access the base layer and (2) the time resource required to fit the base layer will diminish with increasing modulation.

Nevertheless, since (1) and 2) have nonlinear properties, they should be changed as the linear equations to formulate ILP problem.

5. ILP Modeling

We develop the remaining works to change conditions (1) and (2) as ILP model. The following lemma is proposed to change as the linear equations.

Lemma 4. For i [member of] {0,1, ..., I}, [c.sub.i] [member of] {0, [N.sup.+]}, if binary random variable [x.sub.i] [member of] {0,1} has the following condition:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (11)

where [A.sub.i] and [B.sub.i] are the elements of a constant vector and D is a constant and is always larger than [[summation].sup.I.sub.i=1][A.sub.i][B.sub.i][c.sub.i], conditional equation (11) is given as

[Dx.sub.i] [less than or equal to] [I.summation over (i=1)] [A.sub.i][B.sub.i][c.sub.i], (12)

[I.summation over (i=1)] [A.sub.i][B.sub.i][c.sub.i] - D < [x.sub.i]. (13)

Proof. We can prove it easily. Equation (12) means that [x.sub.i] should be 0 if [[summation].sup.I.sub.i=1] [A.sub.i][B.sub.i][c.sub.i] [not equal to] D, and it can be 1 or 0 otherwise. On the contrary to this, (13) means that [x.sub.i] should be 1 if [[summation].sup.I.sub.i=1][A.sub.i][B.sub.i][c.sub.i] = D, and it can be 1 or 0 otherwise. If we use these two equations, (12) and 13), we can guarantee condition (11). Using Lemma 4, the conditions in (1) and 2) are changed as follows.

Theorem 5. [y.sub.l,m] should be satisfied by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (14)

Proof. This can be easily proved by Lemma 4.

Theorem 6. [z.sub.l,m] should be satisfied by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (15)

Proof. This is can be easily proved by Lemma 4.

The ILP problem to maximize the sum of utilities of all users in the wireless multicast service streaming can be formulated as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (16)

with the constraints (4), (7), (8), (9), (10), (14), and (15).

In the worst case, since our method utilizes the same domain as the existing method [10] to find out an optimal solution, the complexity obtained 0(JL + L[M.sup.2]F/[t.sub.M]). O(JL) is the complexity which is precalculated to find out the highest MCS to each node. 0(L[M.sup.2]F/[t.sub.M]) is the complexity to solve [alpha] and [beta] for all 1 [less than or equal to] l [less than or equal to] L, 1 [less than or equal to] m [less than or equal to] M, and 1 [less than or equal to] m [less than or equal to] M. F/[t.sub.M] is the maximum number of slots and [t.sub.M] is the minimum size of a slot. The complexity of the proposed method is pseudopolynomial due to the factor related to the time resource and the number of nodes. Since the complexity is linearly proportional to the number of nodes, the network size does not deteriorate the performance in the proposed methods. Therefore, the complexity of the proposed method is acceptable.

6. Numerical Results

In this section, we present the numerical results for our proposed solution. We consider one base station with 14 mobile users distributed in the circular area from base station. The test is based on the 802.16 m evaluation methodology document [16] for a 3.5 MHz spectrum in 3.5 GHz range. We assume that there are four types of MCSs in the IEEE 802.16 m standard [17]. Table 1 shows the MCSs we use in our test and the number of users who can support each MCS. We assume that, for every scheduling period, the fixed-size packet of 60 bits is transmitted in a wireless channel. Other various settings including MAC/PHY header, ACK, interframe space time, and others are not considered. This is because we aim to provide abstraction of important features of our solutions. Other existing researches [8,10] are also not considered for it. If the setting is required, our solution can use it easily.

In order to analyze the features of our solution, we consider a single video session. Each video session has a fixed layer rate of 800 kb/s, and the number of layers in each session is 8. This is based on the standard of the SVC extension [4] of H.264/MPEG4-AVC. So, each layer can handle 400 packets in a scheduling period because the size of the layer is 30 Kbyte in a scheduling period. We set that [phi] = {1, 0.95,0.9, ..., 0.65} and [[phi].sub.l] = {10,10, ..., 10} for l = {1, ..., 8} based on 13].

We compare our solution with the fixed-slot solution which was solved by dynamic algorithm [10], as the scheduling varies period from 20 ms to 30 ms with interval 1.25 ms. The software package CPLEX is used to find the solution. Table 2 shows the size of a slot to transmit a packet in both solutions and the number of packets that can be transmitted by the method during a slot of the fixed-slot method.

Figure 4 shows the sum of utilities of two solutions. The proposed method enhances the sum of utilities by about 1.9-7.6% compared to the other method. The difference between the two solutions shows an increasing trend. This is because the proposed method assigns more time resource to the low MCSs compared to the other method by reducing the idle time. By detailed observation at 30 ms of frame period, we can understand why the proposed method can enhance the performance. Table 3 specifies the performance difference between the proposed solution and the fixed-size solution at 30 ms of frame period. The sum of utilities of our solution is 6950, while that of the fixed-slot solutions is 7478. Our solution is higher about 7.6%. This is because by eliminating idle time our solution provides second MCS (m = 2) with more slots than those provided by the fixed-slot solution even though both provide the transmission of all the layers.

7. Conclusion

In this paper, we considered and studied the resource allocation problem in SVC video multicast with AMC in wireless networks. First, we assume that all packets have equal length to consider the real video transmission environments. It is also assumed that each MCS has different slot length, which is the minimum time length required to transmit a packet with the corresponding MCS. We formulated a utility function as a piecewise function for ILP modeling using the existing results [11,13]. Finally, we define ILP problem by proposing some lemmas and a theorem to formulate ILP problem. We provide numerical results to show performance difference with [10] under 802.16 m environments. The results show that our methodology enhances overall system throughput by eliminating radio resource waste.

http://dx.doi.org/10.1155/2014/769241

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

Acknowledgment

This research was supported by the Basic Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2012R1A1A2007605).

References

[1] K. Obraczka, "Multicast transport protocols: a survey and taxonomy," IEEE Communications Magazine, vol. 36, no. 1, pp. 94-102, 1998.

[2] J. Kim and D.-H. Cho, "Enhanced adaptive modulation and coding schemes based on multiple channel reportings for wireless multicast systems," in Proceedings of the IEEE 62nd Vehicular Technology Conference (VTC-2005-Fall), vol. 2, pp. 725-729, September 2005.

[3] L. Zhou, H. Wang, S. Lian, Y. Zhang, A. V. Vasilakos, and W. Jing, "Availability-aware multimedia scheduling in heterogeneous wireless networks," IEEE Transactions on Vehicular Technology, vol. 60, no. 3, pp. 1161-1170, 2011.

[4] H. Schwarz, D. Marpe, and T. Wiegand, "Overview of the scalable video coding extension of the H.264/AVC standard," IEEE Transactions on Circuits and Systems for Video Technology, vol. 17, no. 9, pp. 1103-1120, 2007.

[5] Z. Liu, Z. Wu, P. Liu, H. Liu, and Y. Wang, "Layer bargaining: Multicast layered video over wireless networks," IEEE Journal on Selected Areas in Communications, vol. 28, no. 3, pp. 445-455, 2010.

[6] J. Kim, J. Cho, and H. Shin, "Layered resource allocation for video broadcasts over wireless networks," IEEE Transactions on Consumer Electronics, vol. 54, no. 4, pp. 1609-1616, 2008.

[7] H. M. Radha, M. van der Schaar, and Y. Chen, "The MPEG4 fine-grained scalable video coding method for multimedia streaming over IP" IEEE Transactions on Multimedia, vol. 3, no. 1, pp. 53-68, 2001.

[8] S. Deb, S. Jaiswal, and K. Nagaraj, "Real-time video multicast in WiMAX networks," in Proceedings of the 27th IEEE Communications Society Conference on Computer Communications (INFOCOM '08), pp. 2252-2260, April 2008.

[9] D. Wu, Y. T. Hou, and Y.-Q. Zhang, "Scalable video coding and transport over broadband wireless networks," Proceedings of the IEEE, vol. 89, no. 1, pp. 6-20, 2001.

[10] P. Li, H. Zhang, B. Zhao, and S. Rangarajan, "Scalable video multicast with adaptive modulation and coding in broadband wireless data systems," IEEE/ACM Transactions on Networking, vol. 20, no. 1, pp. 57-68, 2012.

[11] K. Stuhlmuller, N. Farber, M. Link, and B. Girod, "Analysis of video transmission over lossy channels," IEEE Journal on Selected Areas in Communications, vol. 18, no. 6, pp. 1012-1032, 2000.

[12] S. Tang and P R. Alface, "Impact of packet loss on H. 264 scalable video coding," in Proceedings of the 5th International Conferences on Advances in Multimedia (MMEDIA '13), pp. 67-73, 2013.

[13] Z. Ma, Z. Liu, M. Xu, and Y. Wang, "Modeling the channel distortion of temporal scalable video," Tech. Rep., Polytechnic Institute of New York University, 2009.

[14] J. Sun, W. Gao, D. Zhao, and W. Li, "On rate-distortion modeling and extraction of H.264/SVC fine-granular scalable video," IEEE Transactions on Circuits and Systems for Video Technology, vol. 19, no. 3, pp. 323-336, 2009.

[15] M. R. Ardestani, A. A. B. Shirazi, and M. R. Hashemi, "Rate-distortion modeling for scalable video coding," in Proceedings of the 17th International Conference on Telecommunications (ICT '10), pp. 923-928, April 2010.

[16] R. Srinivasan, J. Zhuang, L. Jalloul, R. Novak, and J. Park, "IEEE 802.16 m evaluation methodology document (EMD)," IEEE 802.16 Broadband Wireless Access Working Group, 2008.

[17] I. B. W. A. W. Group, "IEEE Standard for local and metropolitan area networks, part 16: air interface for broadband wireless access systems, amendment 3: advanced air interface," IEEE Std 802.16 mTM, 2011.

Dongyul Lee and Chaewoo Lee

School of Electrical and Computer Engineering, Woncheon Hall 432, Ajou University 206, World Cup-ro, Yeongtong-gu, Suwon-si, Gyeonggi-do 443-749, Republic of Korea

Correspondence should be addressed to Dongyul Lee; leedongyull@gmail.com

Received 6 March 2014; Accepted 7 July 2014; Published 3 September 2014

Academic Editor: Gerhard-Wilhelm Weber

TABLE 1: MCS and number of users supporting them. m 1 2 3 4 Modulation BPSK QAM16 QAM64 QAM256 Code rate 3/4 1/2 2/3 3/4 Net PHY bit 2.12 5.64 11.29 13.39 rate (Mbps) The number of users 14 13 8 7 supporting MCS TABLE 2: Slot size of used solution and the comparison of packet number between them. m 1 2 3 4 Slot size of the proposed 28.29 10.62 5.28 4.47 solution ([micro]s) Slot size of fixed-slot 28.29 28.29 28.29 28.29 solution ([micro]s) The number of packets 1 2.67 5.33 6.33 which the proposed method can transmit during a slot of the fixed-slot method TABLE 3: Performance difference between them. m 1 2 3 4 The sum of utilities of 7478 the proposed solution Total used time in 0.0299994 a frame The proposed 11.316 8.496 8.131 2.056 solution (ms) The number of packets 400 800 1540 460 of the proposed solution The sum of utilities 6950 of fixed-slot solution Total used time in 0.02979864 a frame Fixed-slot 11.31 5.658 9.051 3.771 solution (ms) The number of 400 400 1600 800 packets of fixed-slot solution

Printer friendly Cite/link Email Feedback | |

Title Annotation: | Research Article |
---|---|

Author: | Lee, Dongyul; Lee, Chaewoo |

Publication: | The Scientific World Journal |

Article Type: | Report |

Date: | Jan 1, 2014 |

Words: | 4609 |

Previous Article: | Real-time terrain storage generation from multiple sensors towards mobile robot operation interface. |

Next Article: | Does Motor Training of the Nonparetic Side Influences Balance and Function in Chronic Stroke? A Pilot RCT. |

Topics: |