WIRELESS COMMUNICATIONS AND MOBILE COMPUTING Wirel. Commun. Mob. Comput. 2007; 7:9–21 Published online 9 January 2006 in Wiley InterScience (www.interscience.wiley.com). DOI: 10.1002/wcm.296
Optimal dynamic transport selection for wireless portable devices Mohamed Younis*,y , Amit Sardesai and Yaacov Yesha Department of Computer Science and Electrical Engineering, University of Maryland, Baltimore County, Baltimore, M.D. 21250, U.S.A.
Summary Recent technological advances in mobile computing and wireless communication have made portable devices, such as PDA, laptops, and wireless modems to be very compact and affordable. On the other hand, wireless networks have gained such wide popularity that new network infrastructure is continually introduced. It is thus likely that many of the future portable devices will be equipped with multiple wireless modems such as Bluetooth and 802.11 WLAN, in order to increase device inter-operability. The availability of multiple modems can leverage the performance of the communication traffic generated by the applications, for example Internet access. We envision a tool for managing the device connection through these modems. At the core of this tool is an optimization engine that splits packet traffic across a subset of the available transports so that user’s performance metrics are maximized. This paper describes a mathematical model for such an optimization problem considering its applicability to small portable devices. Relevant quality of service (QoS) parameters such as bandwidth, average delay, and energy consumption are covered in the model. The mathematical formulation is validated using a simulated environment. The experimental results have demonstrated the effectiveness of our model and captured the inter-relationship among the quality parameters. Copyright # 2006 John Wiley & Sons, Ltd.
1. Introduction Technological advances in microelectronics and the growing level of integration allowed wireless modems to be energy-efficient and very small in size. Such advances have made these modems to be widely available and affordable for both traditional and portable computing devices. It is thus expected that the future laptop computer and some digital personal assistants to be equipped with multiple types of wireless modems, such as Bluetooth and 802.11 wireless LAN, in order to increase their versatility and adaptability to different networks and environments. However, the availability of multiple modems will require the development of a methodology for the
selection of the most suitable transport for a particular application when more than one transport are feasible candidates. In addition, the simultaneous use of multiple transports can have a positive impact on the response time since packets can be split and sent in parallel over them. Quality of service (QoS) of the network, which means providing consistent, predictable data delivery service at an acceptable cost. It also means the goodness a certain operation is performed with service cost, throughput, energy efficiency, response time, and connection reliability are the QoS metrics that are affected by the transport selection. Therefore, there might be a tradeoff between the services provided by different networks. For example, some transports
*Correspondence to: Mohamed Younis, Department of Computer Science and Electrical Engineering, University of Maryland, Baltimore County, Baltimore, M.D. 21250, U.S.A. y E-mail:
[email protected] Contract/grant sponsor: Aether Systems, Inc. Copyright # 2006 John Wiley & Sons, Ltd.
10
M. YOUNIS, A. SARDESAI AND Y. YESHA
might ensure good throughput while others might provide reliable connections. Thus, the selection of whether a particular network is better than the other is decided by what the user values the most. These metrics are a function of the different parameters,z like bandwidth, delay, jitter, energy consumption, error rate, etc. Since a network may have different parameters, the availability of multiple networks will allow more choices and increase the feasibility of attaining the desired levels of transmission quality. In addition, the simultaneous use of multiple transports will introduce parallelism in the data transmission and thus increase the speed of the communication. For example consider a user downloading a video file or participating in an online conference in a multimedia environment. Typically, the delay per packet should be less than 150 ms and the delay jitter should not exceed 10 ms in order to avoid static frames and maintain lip synchronization. The user will have a choice among the different transports available to him to meet the quality requirements. If none of the transports available to the user can meet such requirements, packets can be split among multiple transports in order to overcome some of the performance shortcoming of some of these transports when individually used. For example, parallel packets transmission on multiple transports would make the effective delay and jitter acceptable. The simultaneous use of multiple wireless transport raises two important issues. The first deals with the methodology of selecting a subset of the transport for consideration based on optimality criteria and subject to user minimum expectation for achieved quality. The second issue is related to supporting the use of multiple connections for transmission and reception of data of a single application. This includes dealing with packet ordering and other related issues in the communication stack. In this paper, we are only concerned with the optimality of transport selection. Other work has addressed the handling of multiple connections [1]. In this paper, we develop a model for calculating the optimal splitting of packets among the available networks by considering the load on the network and the dynamic nature of the different QoS parameters. Optimality is achieved when the highest possible levels of user’s valued QoS metrics are attained. We characterize the model as a function of the number of packets that are to be passed through each network. z
We will refer to them there after as QoS parameters.
Copyright # 2006 John Wiley & Sons, Ltd.
The model is further simplified to a linear integer’s programming problem. Such simplification is highly desired in order to suit the energy and resource constraints of portable wireless devices, which do not afford to consume much of their resources for solving a complex optimization problem in a very dynamic networking environment. Since the traffic condition of the networks is constantly changing due to load and other factors such as radio interference, the values of network QoS parameters also vary. In our framework, we monitor the variability in the network QoS parameters such as delay at the user node. In other words, we rely on the user perceived values of the network quality parameters in order to track deviations from theoretical or published figures. Such approach ensures the consideration of current network load and interference while optimally dividing user requests among the available networks. The paper is organized as follows. In Section 2, we discuss related work. Section 3 describes the tool design and the problem formulation. Section 4 discusses the experimental validation and the analysis of the results. Finally, Section 5 concludes the paper and points out future research directions.
2.
Related Work
Supporting QoS through adaptive resource management has received attention in multiple research areas, most notably the work in the communication and distributed computing community. While, in the communication community, QoS is usually used to mean throughput, reliability, end-to-end transmission delay, etc., the distributed computing community has extended the notion to include computation-related metric such as timeliness. The bulk of the work on supporting QoS metrics in communication networks has considered the issues in just one network. When one network is considered, it is conceivable to manage the different network resources in order to optimize overall network performance or even the performance experienced by a set of users. Multiple techniques can be implemented within a single network to support communication-based QoS requirements [2–8]. However, non-communication based QoS metrics such as cost and energy consumption cannot be managed. Our model deals with multiple transports and thus the performance that the user experiences is the aggregate function of the performance of multiple networks. In addition, the links to Wirel. Commun. Mob. Comput. 2007; 7:9–21
TRANSPORT SELECTION FOR WIRELESS PORTABLE DEVICES
This section describes our approach to optimally divide the packets among the networks. We develop a mathematical model for such optimization problem and analyze the model complexity. We further simplify the model to better suit devices with limited computing and energy resources. First, we discuss the big picture and where our work fits.
3.1.
The Big Picture
We envision a tool that monitors the performance of the different transports and adjust the packet splitting ratio depending on the past experience with the networks. Since the user computing/communication device, when connected through one transport, is just a node in the network, the values of QoS parameters of that network cannot be exactly known. The tool would document the user’s experience. Such experience is to be used by the optimization module in adjusting the split ratio in order to meet optimality criteria. The user interface allows for changing user’s priorities for the different quality parameters. The packet router enforces the packet splitting ratio generated by the optimization module. Figure 1 depicts the interaction between the different modules. Routing packets of a particular source to a destination through multiple connections are not trivial since most widely used network protocols associate the address of the connection to the source. Packets sent from source to destination with different source addresses than the established connection are likely to be
User interface lity ua st Q tere in
Desired quality of service parameters
3. Optimal Transport Selection
Optimization Module Optimal transport utilization
Copyright # 2006 John Wiley & Sons, Ltd.
Tr ansport quality measurements
Transport quality measurements
Model manager
The problem of selecting the optimal capacity usage of multiple transports is a typical resource allocation problem faced in many engineering designs. In most cases, formulation of the allocation problem using a mathematical model requires the most attention. Selecting an optimization algorithm to solve the mathematical model depends on the nature of the model. The model is usually classified based on the nature of both the objective function and the constraints. Models with non-linear objective functions and constraints are the most time consuming to solve.
le ab ev y hi alit Ac qu
the different networks would have varying characteristics and QoS parameters, thus making the packet splitting problem more complex compared with just single-network-based QoS provisioning. The most famous techniques for supporting QoS routing in networks are the differentiated service and bandwidth reservation. Both techniques control one QoS parameter, namely the bandwidth, in order to ensure the achievement of the level of QoS required by the application. Applying differentiated service requires careful queue management at all the nodes on the selected route [9–11]. On the other hand, bandwidth reservation keeps aside enough resources at every node on the route for the user connection [12– 18]. Both techniques are applicable only within the same network and support only communication-based QoS metrics such as end-to-end delay. In our model, we do not control the resources of each of the available networks. Instead, we dynamically adjust the usage profile of these networks, from the user prospective, in order to dynamically cope with changes in the network load and in user demands. In addition, we support QoS metrics such as cost and energy consumption, which are not traditionally considered. The scope of QoS has been extended for large distributed networks to accommodate processing based quality (performance) metrics. The RTARM project is an example of such work [19]. In RTARM, the real-time performance has been added to the QoS metrics, both on the communication and computation level. The approach pursued relies on a middle ware that is employed at every node in order to manage local resources and collaborate with other computing nodes on controlling network-level resources. The middle ware continually monitors resource usage and verifies constraints. If needed, tasks are reallocated among the different computing nodes.
11
Tran sport quality monitor
Packet router
Fig. 1. Interactions among the proposed software modules. Wirel. Commun. Mob. Comput. 2007; 7:9–21
12
M. YOUNIS, A. SARDESAI AND Y. YESHA
dropped. We assume the availability of a network layer protocol that handles such packet routing issue, for example Reference [1]. The optimization process can be envisioned as part of the protocol application layer. This paper is only concerned with the model manager and the optimization module of the tool. 3.2.
Model Formulation
In this subsection, we formulize the problem of packet splitting among different transports as an optimization problem. The objective of the optimization model is to maximize the QoS metrics as a function of the packets allocated to every transport. We further simplify the model in order to limit the computational complexity of the optimization algorithm to fit a mobile computing environment in which a limited number of compute cycles are available. While in the discussion we focus on packet transmission, the formulation is equally applicable to packet reception. Before generating the overall objective function and the constraints for optimal transport selection, let us define the parameters and notations used. m n T Wj
: : : :
Pj
:
UPj
:
Pij
:
meanij : ij
:
Number of transport services available. Number of QoS parameters considered. Total number of packets. User defined weighting factors for aP QoS m parameter j (0 Wj 1.0 and j¼1 Wj ¼ 1). Different QoS parameters considered by the user with j ranging from 1 to n. User specified bound value for each QoS parameter with j ranging from 1 to n. Actual QoS parameter value with i ranging from 1 to m and j ranging from 1 to n. Average value of a particular QoS parameter j over a particular transport i. Standard deviation value of QoS parameter j on transport i.
The problem can be formulated as finding the optimal splitting of the T packets into a1, a2, . . . ,am packets to be transmitted through transport 1 to m, respectively. A precise formulation of the objective function would involve the values of QoS metrics, such as throughput for each network at the time of the packet splitting. Obtaining an exact measure of these QoS metrics for a particular transport would require a complete knowledge and consistent monitoring of the entire network, something a mobile user node cannot perform. Therefore, we have decided to capture the effect of the QoS parameters instead. Copyright # 2006 John Wiley & Sons, Ltd.
The effect of the QoS parameters on performance can be contradicting. For example, to reduce the transmission error rate the device should transmit packets at high power, and thus increase the energy consumption. Given such difficulty in controlling all of the QoS parameters to achieve a positive impact on all metrics, we decided to formulate an objective function ‘F’ that is a weighted average of parameterspecific functions. Since, enhancing the quality of the communication requires minimizing most parameters such delay, energy, etc., we formulate the problem as a minimization problem. Objective functions for parameters such as bandwidth that need to be maximized are transformed into an equivalent minimization formulation. If F1, F2, . . . , Fn are the objective functions for each QoS parameter, the overall objective function can be expressed as: Minimize FðP; a1; ... ;m Þ ¼ W1 F1 ðP1 ; a1; ... ;m Þ þ þ Wn Fn ðPn ; a1; ... ;m Þ The minimization of this function is constrained by the bounds on the values of the QoS parameters specified by the user. m X
ai Pij UPj
i¼1 m X
ai ¼ T ðTotal number of packets in the jobÞ
i¼1
ai 0 8 1 i m; and ai are all integers Given the diverse nature of the QoS parameters, the objective function of every parameter has to be unitless and normalized so that it would take values in (0, 1]. The objective functions for the QoS parameters are defined as follows: Function for Bandwidth: Bandwidth reflects the data transmission rate of a particular transport. If we ignore collisions among the different transports, the bandwidth can be considered an additive quantity. Thus, the objective function for bandwidth can be expressed as: F1 ðP1 ; a1;...;m Þ ¼
m X
BWi ai
i¼1
Wirel. Commun. Mob. Comput. 2007; 7:9–21
TRANSPORT SELECTION FOR WIRELESS PORTABLE DEVICES
Where BWi is the bandwidth offered by transport ‘i’ The normalized and unitless function can be obtained by dividing by BWT, which is the sum of the bandwidths of all transports, that is BWT ¼ P m i¼1 BWi
F1 ðP1 ; a1;...;m Þ ¼ ð1=TÞ
m X BWi i¼1
BWT
BWT
i¼1
ai
ð1Þ
Since such formulation of F2 introduces unwanted complexity to the objective function, we simplify it by considering only the mean latency of every transport. The contribution of the variance will be captured by the jitter function. Thus, using the mean of combined normal distribution: meanLi ai
i¼1
The normalized and unitless function can be obtained by dividing by meanLT, which is the sum of all mean value of Platency of all transports, that is meanLT ¼ m i¼1 meanLi F2 ðP2 ; a1;...;m Þ ¼ ð1=TÞ
m X meanLi i¼1
meanLT
Copyright # 2006 John Wiley & Sons, Ltd.
m X Ci i¼1
ð bound 1 ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi ffi p F2 ðP2 ; a1;...;m Þ ¼ P 2 2 2 m i¼1 ai Li 0 ! Pm x i¼1 ai meanLi ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi pP dx exp m 2 2 2 i¼1 ai Li
F2 ðP2 ; a1;...;m Þ ¼ ð1=TÞ
meanJT
ð2Þ
ð3Þ
CT
ai
ð4Þ
Function for Energy Consumption: Similar to cost and bandwidth, energy is consumed on a per packet basis and is thus additive. F5 ðP5 ; a1;...;m Þ ¼ ð1=TÞ
m X Eti i¼1
ET
ai
ð5Þ
Since the energy consumed per packet for transmission is significantly different from the case of reception, the energy per packet Eti has to be adjusted accordingly. Function for Error Rate: Assuming transmission (reception) error obeys a Poisson distribution and errors on the different transports are independent, the combined error distribution will be again a Poisson distribution with additive means. F6 ðP6 ; a1;...;m Þ ¼
bound X x¼0
e
m 1 X ai meani x! i¼1 Pm i¼1
!x
ai meani
The function F6 can be further simplified by considering the mean error rates for all transports and normalized similar to the latency function. F6 ðP6 ; a1;...;m Þ ¼ ð1=TÞ
m X meanerri i¼1
ai
ai
Function for cost: Similar to bandwidth, cost is considered additive and incurred on a per packet basis. Following similar analysis to the bandwidth, the function for cost can be expressed as: F4 ðP4 ; a1;...;m Þ ¼ ð1=TÞ
Function for Latency: Assuming that the latency on a particular transport obeys a normal distribution function and that the delays on the different transports are independent, the latency of the split packets can be expressed as a normal distribution with average means and variance of all transports.
m X
m X meanJi i¼1
The optimal value is obtained by maximizing F1. Since the packet splitting formulation is a minimization problem, F1 has to be transformed in order to fit into overall objective function. F1 can be expressed as minimization function as follows:
F1 ðP1 ; a1;...;m Þ ¼ 1 ð1=TÞ
Function for Jitter: Similar to the latency, the jitter of the split packets is expressed as a normal distribution. As we have done with the latency function, the simplified and normalized the objective function for jitter is F3 ðP3 ; a1;...;m Þ ¼ ð1=TÞ
ai
m X BWi
13
meanerrT
ai
ð6Þ
The overall objective function can thus be expressed from Equations (1) to (6) as Wirel. Commun. Mob. Comput. 2007; 7:9–21
14
M. YOUNIS, A. SARDESAI AND Y. YESHA
Minimize FðP; a1;...;m Þ ¼ W1 ð1 ð1=TÞ
m X BWi
ai Þ BWT m X meanLi þ W2 ð1=TÞ ai meanLT i¼1 m X meanJi þ W3 ð1=TÞ ai meanJT i¼1 m X Ci þ W4 ð1=TÞ ai CT i¼1 m X Eti þ W5 ð1=TÞ ai ET i¼1 m X meanerri þ W6 ð1=TÞ ai meanerrT i¼1 i¼1
subject to the following constraints m X
ai Pij UPj ;
i¼1
m X
ai ¼ T
different wireless transports have been considered. In the simulation, the network behavior and the dynamic changes of network parameters are modeled using the standard specifications and published performance measurements of the considered transports. The main goals of the simulation-based experiments are: To validate the correctness of the formulation and the capability of the model in capturing the effect of the most important parameters. To show how the model reacts to changes in user’s priorities. Such study can guide the choice of the weighting factors by quantifying the relative impact on the performance caused by a change in one of the parameters. To uncover any dependencies among the QoS parameters. Such investigation can point out weighting factors that possibly lead to equivalent effects and unexpected anomalies caused by certain priority settings.
i¼1
ai 0 8 1 i m; and ai are all integers 4.1. The function F can be characterized as a linear objective function of ai’s with linear inequality constraints. Since the solution has to be integers, the optimization problem is classified as an integer linear programming problem. Many techniques have been proposed in the literature to solve such problem very efficiently [20]. Given the dynamic nature of the network, it would be beneficial to perform the packet splitting on the smallest possible T in order to ensure the freshness of the measures of the QoS parameters on which the optimization is based. On the other hand, the proposed tool is expected to run on resource-constrained portable devices and thus high frequency of running the optimization algorithm can be an issue. Ideally, although not practical due to the excessive overhead, the optimization is performed on a per-packet basis. We envision the number of packets T, which achieves the best gains through splitting on multiple transports with acceptable overhead, would highly depend on the device capabilities and the available transports.
4.
Experimental Validation
We have validated the mathematical model described in the previous section through simulation. Nine Copyright # 2006 John Wiley & Sons, Ltd.
Simulation Design
For every transport considered, a network is simulated. The simulation is based on load-performance relationship for the underlying network. Since a single terminal node cannot predict the internal structure of a network, we believe that the only choice for a node is to reflect on its perception of the network performance relative to the load, to which the node is also contributing. The workload on a network is modeled by the number of user nodes connected to the network. User arrival and departure follow a Poisson process, that is exponential inter-arrival and departure time. Every user generate packets on the network following an exponential distribution. The number of packet generated is picked using a uniform distribution. A network is simulated by means of a single event queue. Events include the generation of new set of packets, the arrival of packets to their destination, a new user joining the network and the departure of an existing user. Events are pre-scheduled using the inter-arrival time. For example, every time a user joins a network the inter-arrival time for the next user is calculated using the exponential distribution and inserted in the event queue. Packet delay is predicted at the time of packet generation based on the current network load. That delay is used to schedule packet arrival at their destination and a delete event is attached to the queue. Wirel. Commun. Mob. Comput. 2007; 7:9–21
TRANSPORT SELECTION FOR WIRELESS PORTABLE DEVICES
No. Packets Delay Time Next Arrival Time 15
0.00025
0.0005
No. Packets Delay Time Next Arrival Time 30
0.000375
0.0007
No. Packets Delay Time Next Arrival Time 15
....
0.0008
Entry
15
Start
"insert" Initialize current time to zero and set all the QoS parameters to values consistent with initial load
Entry "insert" Entry
current time < simulation time
"delete"
No
Stop
Ye s
No. Packets Delay Time Next Arrival Time 20
0.00045
0.0010
Entry
current time > arrival time
"insert"
No
Ye s
No. Packets Delay Time Next Arrival Time 10
....
0.0012
Entry
Increase total load by current # packets, generate new users and packets and calculate next arrival and delay time
"delete"
Fig. 2. Snapshot of the event queue. current time > delay time
No
Ye s
For a packet delete event, the load is adjusted and the next packet generation is scheduled. Figure 2 shows a snapshot of the event queue having different delay values at various instants depending on network load. Figure 3 outlines the queue management procedure. The simulation time and the time unit are parameters of choice. Every time increment, the current time is adjusted and the event queue is checked. In case of matching the schedule of an event, the appropriate action is taken and the process is repeated. It should be noted that there is an event queue for every transport that is considered in the simulation. 4.2.
Decrease total load by current # packets, generate new users and packets, and calculate next arrival and delay time
current time > next user arrival time
Ye s
Generate new users and packets and calculate arrival and delay time
No
current time = current time + increment
Fig. 3. Flow diagram for simulator design.
change with load are based on published performance studies found in References [21–29]. The parameter setting in our experiments are listed in Table I. Energy consumption is estimated based on the average distance between hops in different wireless networks. In our experiments, the selection of the user specified bounds for network parameters are based on multimedia environment where voice or data
Experiment Setup
We have validated our mathematical model using nine transports, namely Bluetooth, IEEE 802.11 Wireless LAN, GSM, GPRS, UMTS, WCDMA, TDMA, TETRA, and Ricochet. The values of the different transport QoS parameters and how these values
Table I. Transport parameter used in the experiment. Networks Bluetooth WLAN GSM RICOCHET GPRS UMTS WCDMA DECT TETRA
Bandwidth (bit/s)
Delay (s)
Jitter (s)
9600 11M 9600 128K 113K 2M 2.4M 2M 28800
0.6375 1.18 0.47 0.47 0.47 0.67 0.47 0.2 0.8
1E-09 0.094 1E-08 0.012 0.08 25E-13 1E-11 6E-08 5E-09
Copyright # 2006 John Wiley & Sons, Ltd.
Cost 0.07 0.005 0.019 0.0512 0.019 0.01 0.01 0.005 0.07
Energy (mJ) 1.445 0.2 1.65 0.3 0.4 1.9 2 2.5 1.8
Error rate 0.05 0.0001 0.0005 0.001 0.01 0.00001 0.00001 0.001 0.05
User arrival rate 10 40 10 10 10 15 20 40 30
Initial load (# users) 20 40 20 20 20 15 40 50 10
Wirel. Commun. Mob. Comput. 2007; 7:9–21
M. YOUNIS, A. SARDESAI AND Y. YESHA
packets are streamed through the different networks. The values of the bounds for delay, error rate, cost, and energy are 0.75 s, 0.0512 packet/s, $0.64, and 1800 mJ respectively [13,18,30–32]. 4.3.
Simulation Results
2.5
Bluetooth WLAN
2 Average delay(s)
16
GSM GPRS
1.5
UMTS WCDMA
1
TDMA TETRA
0.5
Ricochet
We have considered the prime choices for the weighting factors to show how performance parameters change with number of packets. The weighting factors of each parameter for each setup are specified in the caption of the respective graph. The performances resulting from packet splitting is referred to as combined network. Figures 4 and 6 represent the curves for average delay versus the number of packets, while Figures 5 and 7 represent the curves for energy consumption versus the number of packets. For these Figures, the weighting factors for only two QoS parameters are considered while resetting the weighting factors of the other parameters to zero. The graphs of Figures 4 and 5 have less priority for delay than for energy consumption. Figure 4 shows that the delay for the case of packet splitting is less than the delay incurred using any of the other networks individually. This is mainly due to parallelism in packet transmission. In Figure 5, 2.5
Bluetooth WLAN GSM GPRS
1.5
UMTS WCDMA
1
TDMA TETRA
0.5
Ricochet
0
Combined
0
200
400
600
800
1000
Number of packets
Fig. 4. Average delay versus # packets, weighting factors delay ¼ 0.2, energy ¼ 0.8, rest are 0.0’s. Energy Consumption (mJ)
2500 2000
GSM GPRS
1500
UMTS WCDMA
1000
TDMA TETRA
500
Ricochet
0
Combined
0
200
400
600
800
1000
Number of packets
Fig. 5. Energy consumption versus # packets, weighting factors delay ¼ 0.2, energy ¼ 0.8, rest are 0.0’s. Copyright # 2006 John Wiley & Sons, Ltd.
200
400
600
800
1000
Number of packets
Fig. 6. Average delay versus # packets, weighting factors delay ¼ 0.8, energy ¼ 0.2, rest are 0.0’s.
the curve for combined energy consumption is less than most of the other curves. This is because energy consumption is given high priority in Figure 5. Comparing Figures 4 and 6, we see that delay curve is lower in Figure 6 since more priority is given to delay, and the networks with the best delay value are selected. Meanwhile, the curve for energy consumption in Figure 7 is higher than that of Figure 5 since priority for the energy consumption factor is lowered. In the case of Figure 5, most packets are sent through the WLAN network, which has the least energy while in the case of Figure 7, most packets are sent through the DECT network, which has least delay. We can see that the delay curve of the combined network in both cases is lower than most other curves due to parallelism. Even though we give more priority to other parameters, the delay curve is always less. Therefore, delay can be assigned low weight since it is enhanced anyway by parallelism. It is worth noting that similar observations could be made when we considered delay and cost [33]. Figure 8 shows the change in the average delay with respect to the number of packets while considering only the weighting factors for delay and bandwidth. Even though the values of the weighting factors of
2500
Bluetooth WLAN
Combined
0
Energy Consumption (mJ)
Average delay(s)
2
0
Bluetooth WLAN
2000
GSM GPRS
1500
UMTS WCDMA
1000
TDMA TETRA
500
Ricochet
0
Combined
0
200
400
600
800
1000
Number of packets
Fig. 7. Energy consumption versus # packets, weighting factors delay ¼ 0.8, energy ¼ 0.2, rest are 0.0’s. Wirel. Commun. Mob. Comput. 2007; 7:9–21
TRANSPORT SELECTION FOR WIRELESS PORTABLE DEVICES 2.5
17
8
Bluetooth
Bluetooth WLAN
WLAN GSM GPRS
1.5
UMTS WCDMA
1
GSM
6
Jitter (s)
Average delay(s)
2
GPRS UMTS
4
WCDMA TDMA
TDMA
2
TETRA
0.5
TETRA Ricochet
Ricochet
0
0
Combined
0
200
400
600
800
1000
Combined
0
200
400
600
800
1000
Numberof packets
Number of packets
Fig. 8. Average delay versus # packets for weight factors delay ¼ 0.2, bandwidth ¼ 0.8, rest are 0.0’s, delay ¼ 0.6, bandwidth ¼ 0.4, rest are 0.0’s.
Fig. 10. Average Jitter versus # packets for weighting factors jitter ¼ 0.2, delay ¼ 0.4, rest are 0.1’s, jitter ¼ 0.4, delay ¼ 0.2, rest are 0.1’s.
bandwidth and delay were changed, we have founded that the average delay experienced is almost the same. Given the closeness of the results obtained only one figure is included. Such behavior stays consistent as long as the delay factor is considered, that is using non-zero weight. A non-zero weight for the delay forces the use of multiple transports and enhances the response time through parallelism. Such results suggest the inter-dependency between the delay and bandwidth parameters and thus the weighting factor of the bandwidth factor can be set appropriately as long as the delay parameter is randomly assigned nonzero value. Figures 9 and 10 capture the change in the values of average delay and jitter with respect to the number of packets. From these figures, we see that even though the weighting factors of jitter and delay are interchanged, the impact on both jitter and delay with respect to the number of packets remains the same. This indicates the inert-dependency between the jitter and delay parameters delay, similar to the earlier case of delay and bandwidth.
Considering the bandwidth and jitter parameters, Figures 11 and 13 show the relationship between average delay and the number of packets, while Figures 12 and 14 represent the curves for jitter versus the number of packets. In the case of jitter, not all curves are shown because there is a large variation in values of jitter for the different networks. It is clear in Figures 11 and 13 that the delay curve for the combined network is less than the delay curve for other networks. The reduction in delay is expected given the packets splitting among multiple transports. 2.5
Bluetooth WLAN
Average delay(s)
2
GSM GPRS
1.5
UMTS WCDMA
1
TDMA TETRA
0.5
Ricochet
0
Combined
0
200
400
600
800
1000
Numberof packets
Fig. 11. Average delay versus # packets, weighting factors bandwidth ¼ 0.4, jitter ¼ 0.2, rest are 0.1’s. 2.5
Bluetooth
8
WLAN
Bluetooth
GSM
WLAN
6
GPRS
1.5
GSM
UMTS WCDMA
1
TDMA TETRA
0.5
GPRS
Jitter (s)
Average delay(s)
2
4
UMTS WCDMA
2
TDMA
Ricochet
0
Combined
0
200
400
600
800
TETRA
0
1000
Numberof packets
Ricochet
0
200
400
600
800
1000
Combined
-2
Numberof packets
Fig. 9. Average delay versus # packets for weighting factors jitter ¼ 0.2, delay ¼ 0.4, rest are 0.1’s, jitter ¼ 0.4, delay ¼ 0.2, rest are 0.1’s. Copyright # 2006 John Wiley & Sons, Ltd.
Fig. 12. Jitter versus # packets, weighting factors bandwidth ¼ 0.4, jitter ¼ 0.2, rest are 0.1’s. Wirel. Commun. Mob. Comput. 2007; 7:9–21
18
M. YOUNIS, A. SARDESAI AND Y. YESHA
2.5
Bluetooth WLAN
Average delay(s)
2
GSM GPRS
1.5
UMTS WCDMA
1
TDMA TETRA
0.5
Ricochet
0
Combined
0
200
400
600
800
1000
Numberof packets
Fig. 13. Average delay versus # packets, weighting factors bandwidth ¼ 0.2, jitter ¼ 0.4, rest are 0.1’s.
The delay curve in Figure 13 is a little bit higher than Figure 11 showing the superior effectiveness of elevating the bandwidth to the jitter priority in enhancing the average delay. Comparing Figures 12 and 14, we find that the jitter curve has increased when more priority is given to the jitter parameter. This is opposite to what is expected since the jitter curve should have decreases when the priority of jitter is increased. Such unexpected performance is because less number of networks is selected when the bandwidth factor is 0.2 (jitter factor ¼ 0.4) compared to the case of 0.4 (jitter factor ¼ 0.2). Since fewer networks are selected, the net delay and jitter of the combined network increases. For additional experimental results involving other combinations of parameters settings, the reader is referred to Reference [33]. 4.4.
Parameters Setting
Based on our experience with the experiments and conclusions drawn from the simulation results, we can make the following remarks about QoS measurements, parameters setting, and handling conflicting goals in practice: 8
Bluetooth WLAN GSM
Jitter (s)
6
GPRS UMTS
4
From the experiments, we conclude that the weighing factor for the delay parameter and that of either the bandwidth or the jitter parameter would have equivalent effect on the delay metric. That is to say focusing on the jitter or the bandwidth would have positive impact on delay, with the bandwidth factor demonstrating more effectiveness. However, it should be noted that favoring the delay factor does not necessarily enhance both the bandwidth and the jitter. It is recommended to manipulate the priority of the bandwidth parameter when the device connects to new transports since there would be no experience with the transport at that moment. During the use of the transport the device will establish statistics regarding the transport and controlling the priority of the other parameters would be more appropriate. Collecting the statistics about a particular transport can be tricky. Given the dynamic nature of traffic in wireless ad hoc and cellular infrastructure, a node perception about a particular transport does not usually hold for long duration and continual assessment would be needed. On the other hand, collecting statistics imposes overhead and requires experiencing all transports, even those for which connections are not established. Thus, the frequency of re-assessing a transport is subject to a tradeoff and is expected to depend heavily on the node and available transports. For applications that would favor the consideration of the cost or energy parameters, the delay factor can be given lower priority relying on the simultaneous packet transmission in minimizing the average packet delay. To force packet splitting and avoid going with the least cost or energy transport, a delay constraint should be imposed or a very small weight can be assigned to the delay factor. Contradicting factors such as energy and error rate can be effectively managed with the inclusion of appropriate constraints and the use of equal weights or picking only one factor for consideration (zero weight for the other factor). Our model then will cope with the minimal requirements and pursue transport selection to optimize the valued factors.
WCDMA
c
TDMA
2
TETRA Ricochet
0
Combined
0
200
400
600
800
Number of packets
Fig. 14. Jitter versus # packets, weighting factors bandwidth ¼ 0.2, jitter ¼ 0.4, rest are 0.1’s. Copyright # 2006 John Wiley & Sons, Ltd.
5.
Conclusions and Future Work
1000
Technological advancements in the mobile computing have foiled the development of new wireless modems in order to connect such devices to network Wirel. Commun. Mob. Comput. 2007; 7:9–21
TRANSPORT SELECTION FOR WIRELESS PORTABLE DEVICES
infrastructure while the user is on the move. Many wireless transports are currently available such the IEEE 802.11 wireless LAN and Bluetooth, and more are being developed. The cost and size of these modems are decreasing so rapidly that it is expected for future portable devices to be equipped with multiple of these modems in order to ensure user access to the diverse network infrastructure. The availability of these modems presents an opportunity for better user experience with applications that requires network access. Multiple of these transports can be simultaneously used to meet and even exceed user expectation regarding the quality of the communication. In this paper, we have developed a mathematical model for packet splitting across multiple transports. The model captures the effect of common parameters that control the quality of service attained from a typical network. These parameters include bandwidth, average delay, delay jitter, etc. The model is further simplified to suit the energy and computationally constrained portable devices. The model is validated through simulation. The simulation results have demonstrated the effectiveness of our approach and the performance gains that the user application can achieve. The experiments clearly have indicated that the average delay is consistently better than the case of using a single transport. Such significant delay reduction is mainly due to the parallel usage of multiple transports. In addition, the experiments have captured dependency among the different QoS parameters and provided guidelines on how priorities can be assigned. The work presented in this paper can be extended by taking into consideration the resources consumed by the optimization software module itself into the model. Since portable devices are constrained in energy supply and computation capacity, the gain achieved by the optimization algorithm has to be qualified using the resources consumed. Another possible extension is by investigating the frequency of running the optimization. Given the dynamic environment that portable devices operate in, changes in the network quality parameters can be very often and there will be a tradeoff between the frequency of running the algorithm to adapt to these changes and the overhead incurred when running the optimizer. Acknowledgment The authors are indebted to Aether Systems, Inc., for funding this research work and to Professor D. Phatak for his constructive comments. Copyright # 2006 John Wiley & Sons, Ltd.
19
References 1. Phatak DS, Goff T. A novel mechanism for data streaming across multiple IP links for improving throughput and reliability in mobile environments. In Proceedings of the IEEE INFOCOM’02, New York, NY, June 2002. 2. Chiang M, O’Neill D, Julian D, Boyd S. Resource Allocation for QoS provisioning in Wireless Adhoc networks. In Proceedings of IEEE GLOBECOM, San Antonio, TX, November 2001. 3. Rajkumar R, Lee C, Lehoczky J, Siewiorek D. Practical solutions for QoS-based resource allocation problems. In Proceedings of the IEEE Real-Time Systems Symposium, Madrid, Spain, December 1998. 4. Lee C, Lehoczky J, Rajkumar R, Siewiorek D. On quality of service optimization with discrete QoS Options. In Proceedings of the IEEE Real-time Technology and Applications Symposium, Vancouver, Canada, June 1999. 5. Qiu L, Bahl P, Adya A. The effect of first-hop wireless bandwidth allocation on end-to-end network performance. In Proceedings of the 12th International Workshop on Network and Operating Systems Support for Digital Audio and Video (NOSSDAV), Miami Beach, FL, May 2002. 6. Naik A, Siegel H, Chong E. Dynamic resource allocation for classes of prioritized session and data requests in preemptive heterogeneous networks. In Proceedings of the International Conference on Parallel and Distributed Processing Technologies and Applications (PDPTA 2001), Las Vegas, NV, June 2001. 7. Choi S, Shin K. Predictive and adaptive bandwidth reservation for handoffs in QoS-sensitive cellular networks. In Proceedings of the ACM SIGCOMM’98, Vancouver, Canada, August 1998. 8. Das S, Perkins C, Royer E. Performance comparison of two on-demand routing protocols for ad hoc networks. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM), March 2000. 9. Ogawa J, Nomura Y. A simple resource management architecture for differentiated services. In Proceedings of the Internet Conference (INET 2000), Yokohama, Japan, July 2000. 10. Mahajan M, Parashar M. Managing QoS for multimedia applications in a differentiated services environment. In Proceedings of the 4th Annual International Workshop on Active Middleware Services (AMS’02), Edinburgh, United Kingdom, July 2002. 11. Fulp E, Reeves D. Optimal provisioning and pricing of differentiated services using QoS class promotion. In Proceedings of the INFORMATIK Workshop on Advanced Internet Charging and QoS Technology (ICQT’01), 2001. 12. Pandey V, Ghosal D, Mukherjee B. Comparison of channel partitioning strategies in single- and two-tier cellular networks. In Proceeding of IEEE Conference on Computer Communications (INFOCOM’98), San Francisco, CA, 1998. 13. Popovici E, Borcoci E, Constantin A. Multimedia oriented— transport architectures and QoS management: models and simulation studies in estelle. Research Report No: 000 06— LOR, Telecommunication Networks Department, University of Bucharest, September 2000. (http://www-lor.int-evry.fr/ idemcop/uk/real-cs/mm-taqm/download/mm-exp-estelle.pdf) 14. Hoo G, Johnston W. QoS as middleware: bandwidth reservation system design. In Proceedings of the 8th IEEE International Symposium on High Performance Distributed Computing, Redondo Beach, CA, August 1999. 15. Das SK, Jayaram R, Kakani NK, Sen SK. A call admission and control scheme for quality of service (QoS) provisioning in next generation wireless networks. Wireless Networks 2000; 6(1): 17–30. 16. Cheng ST, Chen IR, Chen CM. A study of self-adjusting quality of service control schemes. In Proceedings of the Winter Simulation Conference (WSC’98), Washington DC, December 1998. Wirel. Commun. Mob. Comput. 2007; 7:9–21
20
M. YOUNIS, A. SARDESAI AND Y. YESHA
17. Prakash R, Shivaratri NG, Singhal M. Distributed dynamic channel allocation for mobile computing. In Proceedings of the 14th ACM Symposium on Principles of Distributed Computing (PODC), Ottawa, Canada, August 1995. 18. Havinga P, Smit G. Mobile multimedia systems. In Chapter 15 of Electronic Business and Education, Recent Advances in Internet Infrastructures, Chin W et al. (eds). Kluwer Academic Publishers: Boston, 2001; 319–360. 19. Rosu ID, Schwan K, Yalamanchili S, Jha R. On adaptive resource allocation for complex real-time applications. In Proceedings of the 18th IEEE Real-Time Systems Symposium, San Francisco, December 1997. 20. Nemhauser G, Wolsey L. Integer and Combinatorial Optimization. Wiley: New York, 1999. 21. Bluetooth i. Golmie N, Chevrollier N. Techniques to improve Bluetooth performance in interference environments. In Proceedings of MILCOM 2001, McLean, VA, October 2001. ii. Lim Y, Kim J, Min SL, Ma JS. Performance Evaluation of the Bluetooth based Public Internet Access Point. In Proceedings of the 15th International Conference on Information Networking (ICOIN’01), Beppu, Japan, February 2001. iii. http://www.us.design-reuse.com/news/news4288.html 22. 802.11 Wireless LAN i. Anastasi G, De Stefano E, Lenzini L. QoS provided by the IEEE 802.11 wireless LAN to advanced data applications: a Simulation Analysis. ACM/Baltzer Wireless Networks 2000; 6(2): 99–108. ii. Chow C, Leung V. Performance of IEEE 802.11 medium access control protocol over a wireless local area network with distributed radio bridges. In Proceedings of the Wireless Communication Networks Conference (WCNC), New Orleans, LA, September 1999. iii. Ng CH, Chow J, Trajkovic L. Performance evaluation of the TCP over WLAN 802.11 with the Snoop performance enhancing proxy. In Proceedings of OPNETWORK 2002, Washington, DC, August 2002. iv. Leang L, Liew J, Seah W. Experimentation of TCP Schemes over GPRS & WLAN. In Proceedings of the 4th IEEE Conference on Mobile and Wireless Communications Networks (MWCN 2002), Stockholm, Sweden, September 2002. v. Birkeland T, Nilsson F. Limitations in performance for WLAN technologies. Master thesis in Information and Communication Technology, Agder University College, Norway, May 2002. vi. http://www.tno.nl/instit/fel/ts/resources/simulation_ofWLAN. pdf 23. Ricochet i. http://www.wherry.com/gadgets/ricochet/ ii. http://daedalus.cs.berkeley.edu/talks/retreat.6.96/Metricom.pdf iii. Stemm M, Katz RH. Measuring and reducing energy consumption of network interfaces in hand-held devices. IEICE Transactions on Communications 1997; E80-B(8): 1125– 1131. 24. UMTS i. http://www.nt.tuwien.ac.at/mobile/projects/UMTS/en/ ii. http://www.ftw.at/Dokumente/011130a.pdf 25. TETRA i. http://www.acterna.com/technical_resources/downloads/datasheets/4032tetrapol_ds_ae.pdf ii. http://www.tetrapol.com
Copyright # 2006 John Wiley & Sons, Ltd.
iii. Kuypers D, Sievering P, Steppler M. Traffic performance evaluation of TETRA and TETRAPOL. In Proceedings of the 10th Aachen Symposium on Signal Theory, Aachen, Germany, September 2001. 26. GPRS i. http://www.gsm.org.uk/gprs.htm ii. Arau´jo H, Costa J, Correia L. Analysis of a Traffic Model for GSM/GPRS. In Proceedings of the 3rd Conference on Telecommunications, Figueira da Foz, Portugal, April 2001. iii. Stuckmann P, Ehlers N, Wouters B. GPRS traffic performance measurements. In Proceedings of the IEEE Vehicular Technology Conference (VTC 2002), Vancouver, Canada, September 2002. iv. Saija D, Toniatti T. Performance evaluation of GPRS (Generic Packet Radio Service) radio access with quality of service provision. In Proceedings of the 21st International Conference on Distributed Computing Systems (ICDCS), Phoenix, Arizona, April 2001. v. Foh C, et al. Modeling and Performance Evaluation of GPRS. In Proceedings of IEEE Vehicular Technology Conference (VTC 2001), Rhodes, Greece, May 2001. 27. GSM i. Ajib W, Godlewski P. Service disciplines performance for best-effort policies in packet-switching wireless cellular networks. In Proceedings of IEEE Annual Vehicular Technology Conference (VTC 2000), Tokyo, Japan, May 2000. ii. http://wireless.agilent.com/rfcomms/refdocs/gsm/hpib_fetch_ berror.html iii. http://www.tele-servizi.com/janus/engfield2.html 28. DECT i. Zhang H, Yum TP. A dynamic reservation protocol for prioritized multirate mobile data services based on DECT air interface. IEEE transactions on Vehicular Technology 2000; 49(2): 672–676. ii. http://www.digitaltalkback.com/netscape/intromain.htm iii. http://www.comlab.hut.fi/opetus/260/111215data.pdf 29. WCDMA i. Matis K. Multilevel simulation of WCDMA systems for thirdgeneration wireless applications. Technical report, ICUCOM Corporation, http://www.sss-mag.com/pdf/wcdma.pdf ii. Latva-aho M. Bit error probability analysis for FRAMES WCDMA downlink receivers. IEEE Transactions on Vehicular Technology 1998; 47(4): 1119–1133. iii. Gu X, Olafsson S. A simplified and accurate method to analyse a code division multiple-access performance. In Proceedings of the Annual London Communication Symposium (LC 2000), September 2000. iv. http://www.datum.com/pdfs/datum.pdf 30. Chandra S. Wireless network interface energy consumption implications of popular streaming formats. In Proceedings of the Symposium on Multimedia Computing and Networking (MMCN), San Jose, CA, January 2002. 31. Krashinsky R, Balakrishnan H. Minimizing energy for wireless web access with bounded slowdown. In Proceedings of ACM MobiCom 2002, Atlanta, GA, September 2002. 32. Yuan W, Nahrstedt K, Gu X. Coordinating energy aware adaptation of multimedia applications and hardware resource. In Proceedings of 9th the ACM Multimedia Middleware Workshop, Ottawa, Canada, October 2001. 33. Sardesai A. Optimal dynamic transport selection for mobile computing. MS Thesis, Department of Computer Science and Electrical Engineering, University of Maryland Baltimore County, 2002.
Wirel. Commun. Mob. Comput. 2007; 7:9–21
TRANSPORT SELECTION FOR WIRELESS PORTABLE DEVICES
Authors’ Biographies Mohamed F. Younis received his B.S. degree in Computer Science and M.S. in Engineering Mathematics from Alexandria University in Egypt in 1987 and 1992, respectively. In 1996, he received his Ph.D. in Computer Science from New Jersey Institute of Technology. He is currently an assistant professor in the Department of Computer Science and Electrical Engineering at the University of Maryland Baltimore County (UMBC). Before joining UMBC, he was with the Advanced Systems Technology Group, an Aerospace Electronic Systems R&D organization of Honeywell International, Inc. While at Honeywell, he led multiple projects for building integrated fault tolerant avionics in which a novel architecture and an operating system were developed. This new technology has been incorporated by Honeywell in multiple products and has received worldwide recognition by both the research and the engineering communities. He also participated in the development of the redundancy management system, which is a key component of the Vehicle and Mission Computer for NASA X-33 space launch vehicle. Dr Younis’ technical interest includes network architectures and protocols, embedded systems, fault tolerant computing, and distributed real-time systems. Dr Younis has four
Copyright # 2006 John Wiley & Sons, Ltd.
21
granted and three pending patents. He served on multiple technical committees and published over 60 technical papers in refereed conferences and journals. Amit Sardesai received his bachelor degree in Computer Science from the University of Mumbai, India and his M.S. degree in Computer Science from the University of Maryland Baltimore County. He is currently pursing his Ph.D. in Computer Science at the University of Florida. His research interests include wireless networks, distributed computation, web services, and databases. Yaacov Yesha is a professor at the Department of Computer Science and Electrical Engineering at the University of Maryland Baltimore County. He received his Ph.D. in Computer Science in 1979 from the Weizmann Institute of Science. His interests include mobile computing, wireless networks, and software testing. Yaacov Yesha was a program vice chair or a program committee member for several scientific conferences.
Wirel. Commun. Mob. Comput. 2007; 7:9–21
