An MADM Network Selection Approach For Heterogeneous Network

An MADM Network Selection Approach For Next Generation Heterogeneous Networks

 

Abstract- Next generation wireless networks will consist of different types of radio access technologies. Emerging diverse applications have attracted a lot of users. Therefore, having the best connectivity anytime anywhere has become an important issue. Users would like to have continuous high quality network connection even when they handover from one network type to the other. Each access technology has its own features and service quality. In this regard, when there is a handover, it is important to choose the most suitable network based on user needs. Different algorithms have been proposed for network selection. Multi Attribute Decision Making (MADM) methods are widely used due to their precision and low computational complexity. In this paper, usual normalization methods used in network selection and their drawbacks are presented and a new method, by taking user preferences and application needs into account, is proposed. Based on the proposed normalization method, a new decision process is suggested which is based on ELECTRE II algorithm. Our proposed method considers the dynamic nature of wireless networks and the uncertainty in the collected network performance metrics. Simulation results show that using the proposed handover decision process, the probability of ranking abnormality, which is a common drawback of MADM methods, is reduced significantly compared to other methods such as SAW, GRA and TOPSIS and the decision algorithm is more stable in terms of sensitivity to change in the amounts of decision criteria.

Keywords-HetNets: MADM: Vertical HO; Normalization

I. INTRODUCTION

Today mobile handsets like advanced cellphones, PDAs and tablets have become an inseparable part of our daily lives. By having internet connectivity they offer various applications like E-commerce, cloud computing, navigation, online gaming, etc. Along with this variety, number of users is increasing rapidly, it has been estimated that monthly mobile traffic will be more than 15 exabytes by 2018. This factor force the operators to cope with this huge traffic without much increase in service cost. In this context, having connectivity at anytime anyplace is not an issue anymore in most parts of the world but offering services suitable for different types of applications with guaranteed QoS is a challenge now [2, 3]. Next generation networks will consist of different radio access technologies (RATs) and Mobile handsets are equipped with multiple interfaces. These access networks include different types such as Global System for Mobile communication (GSM), Code Division Multiple Access (CDMA), Long Term Evolution (LTE), worldwide interoperability for microwave access (WiMAX) and LAN networks like Wi-Fi. Each access technology have its own features and service quality like bitrate, delay, cost etc. None of current RATs offer high quality wide coverage, cost-effective services. Because of the dynamic nature of the wireless networks, user mobility and time varying user’s needs, mobile nodes (MNs) may need to change the RAT they are attached to once a while. The act of changing point of attachment (PoA) from one RAT to another is called vertical handover (VH). VH process is divided into three phases including initiation, decision and execution. In the initiation phase, due to the low received signal strength (RSS) or reduction in service quality MN is triggered to change the PoA. Initiation phase answers the questions like when and where to perform handover. The most important part of the handover process is the decision phase in which the best available network should be chosen based on the user preferences, network characteristics, user mobility, etc. Therefore having the ability and intelligence to choose the most suitable network in this phase is a prominent factor. Execution phase mainly include transferring the current session to the new PoA and finally releasing the resources of the old network.

Network selection is a complex problem and one of the major mobile handsets limitations is battery life. Therefore, proposing an algorithm with fewer computational complexity becomes important [1]. MADM algorithms have low complexity and high precision. They capture different parameters (e.g., QoS, cost, security, user velocity) and select the most suitable RAT. They are capable of taking into account wide range of parameters even when they may be contradictory to each o

weighting (SAW) [4, 5], VIKOR, multiplicative weighting (MEW) [4, 5], gray relational analysis (GRA) [4, 5], TOPSIS [4, 5], fuzzy TOPSIS (FT) [9] and AHP [4, 7]. Due to the vagueness of determining wireless network parameters, fuzzy logic, where linguistic terms and fuzzy numbers are used, is often combined with mentioned MADM algorithms [8, 9 and 10]. Game theory is often used for solving network selection problem. They model the users (or networks) as players, each having a strategy set while trying to reach a mutual acceptable solution. These methods have a problem of long time convergence and high complexity [11]. Despite the precision and simplicity of MADM methods there are some weaknesses that need to be covered like load distribution policy, ranking abnormality and dynamic nature of wireless environment.

In this paper we propose an algorithm based on ELECTRE II method which takes into account the uncertainty of the performance of each network with respect to different criteria. Load distribution factor has been considered. Results show improvements compared to GRA, TOPSIS and SAW methods in terms of ranking abnormality probability and stability.

The rest of this paper is organized as follows. Section II system model is discussed. Section III presents the proposed algorithm for network. Section IV describes the simulation scenario and results. Finally, conclusion is represented in section V.

II. SYSTEM MODEL

We consider a heterogeneous network consisting of different RATs having overlapped coverage areas in some or most parts of the environment. Each MN is equipped with different interfaces, being able to connect to different RATs. After initiation phase, MN should discover available networks, their related features and service qualities. For obtaining aforementioned information we use MIIS service from IEEE 802.21 standard. MIIS provides a framework in which a Media Independent Handover Function (MIHF) entity, which in this case is the MN, can obtain information about the networks in a local or remote geographical area. This information helps the MN to facilitate the decision process [12].

Consider we are in the coverage area of M networks with N attributes which are expressed as 𝑁𝑁={𝑁𝑁1,𝑁𝑁2,…,𝑁𝑁𝑀𝑀} and 𝐴𝐴={𝐴𝐴1,𝐴𝐴2,…,𝐴𝐴𝑁𝑁} respectively. Here we use throughput, delay, jitter, packet loss, cost, security and network load as the criteria. Considering network load as a criterion prevents the unbalanced distribution of the users among candidate networks which leads to better QoS and lower energy consumption. Unbalanced loading can cause excessive HOs. As an example assume there are several networks with overlapped coverage areas with different priorities while one of them, we call it A, has the highest rank among others. For simplicity we assume that all the users being in that area require the same level of performance and have the same user preferences. Because of the highest score, all users try to connect to A, but when number of users increases, network A becomes congested gradually and users will see a degradation in service quality which may trigger some of them to perform a HO. This process may happen again for another network which results in increased number of HOs. This increase causes extra energy consumption, delay and packet loss. In this paper, method of obtaining weights of the criteria used in network selection is not discussed. For any MADM algorithm a decision matrix, called X (1), is built. Element 𝑥𝑥ð‘-ð‘-ð‘-ð‘- of X shows the performance of network i with respect to attribute j. Each criterion has its own measure unit. In order to be able to compare these attributes, elements of X should be normalized. Normalization method will be discussed in section III, subsection A

𝑋𝑋=􀵥𝑥𝑥11⋯𝑥𝑥1𝑁𝑁⋮⋱⋮𝑥𝑥𝑀𝑀1⋯𝑥𝑥𝑀𝑀𝑀 􀵩 (1)

In network selection problem, we have two kinds of attributes namely compensable and non-compensable. The first group are the ones like throughput and security which large amount of any of them can compensate the scarcity of others in scoring phase of the alternatives. Non-compensable attributes must be above a certain threshold and increase in the amount of no other criterion can fix its absence. RSS can be an example of non-compensable attributes which in its absence, we can’t talk about how high the throughput is. Criteria used in MADM algorithms are the compensable ones. Therefore, any change in upward or downward direction of the attributes may change the ranking order and scores. One of the drawbacks of current solutions is that, when utility of a criterion decreases by any amount, level of compensation by gain in other criteria is unlimited.

III. PROPOSED SCHEME

A. normalization of the attributes

Each attribute has its own measure unit. Therefore, normalization is a necessary step for network selection. There are two types of attributes; cost (downward) and benefit (upward) attributes. Increase in the amount of upward attributes is desirable while in downward attributes the situation is vice versa. Several normalization methods have been proposed listed in table 1 [1]. 𝑣𝑣ð‘-ð‘-ð‘-ð‘- is the normalized value of 𝑥𝑥ð‘-ð‘-ð‘-ð‘- and Λð‘- represents the nominal value of attribute j. In decision phase, when one or several alternatives are added/removed from the candidate list, the priority of remaining alternatives may change. This unpleasant phenomenon is called ranking abnormality. The main causes of ranking abnormality is related to the normalization and decision algorithm. All methods given in table 1, use floating points along the way of obtaining normalized values. They use maximum, minimum or sum of 𝑥𝑥ð‘-ð‘-ð‘-ð‘- in their methods, as a result when one or several alternatives are removedadded, normalized values may change. As an example consider there are 5 available networks with 5 different delay values brought in table 2. According to max-min method the normalized values for networks 1-5 would be 1, 0.974, 0.934, 0.8, and 0 respectively. Now imagine network 5 is eliminated from available alternatives, the new normalized values for

1-4 would be 1, 0.867, 0.667 and 0. As you can see the distance between network 3 and 4 has changed from 0.134 to 0.667. This could result in the change of the ranking order. This is true for other methods mentioned in table 1 too. So, one solution could be to set the maximum and minimum of each attribute to fixed points (for example an upper and lower limit).

Setting fixed point for normalization has its own drawback too. Consider we have a set of available alternatives 𝑁𝑁={𝑁𝑁1 𝑁𝑁2}. For simplicity, we consider only delay and throughput for network selection. SAW algorithm with equal weights for both criteria and max-min method with fixed points for normalization is used. Table 3 shows the normalized values for network 𝐴𝐴1 and 𝐴𝐴2.

Table 3. Normalized values for networks 𝑁𝑁1 and 𝑁𝑁2

Criteria

𝑁𝑁1

𝑁𝑁2

Delay

0.35

0.45

Throughput

0.80

0.65

𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑁𝑁1=12Ã-0.35+12Ã-0.80=0.575

𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠𝑠 𝑁𝑁2=12Ã-0.45+12Ã-0.65=0.55

We can see that 𝑁𝑁1 gets a higher score than 𝑁𝑁2. But assume although 𝑁𝑁1 has a higher throughput but both networks satisfy user’s needs in terms of that criterion. Now we have two networks, one having a better delay quality than the other (𝑁𝑁2 better than 𝑁𝑁1) but the normalization method led us to choose 𝑁𝑁1wrongly. This problem was caused by the fact that the criteria were normalized without considering user (application) needs. In order to consider user needs, we propose a utility based normalization method taking into account different traffic classes’ requirements.

In order to be able to normalize the criteria elastically based on user’s needs, we propose a novel normalization function 𝑛 (𝑥𝑥) with five adjustable parameters. This function enables us to consider different traffic features and user preferences. Following assumptions have been made in 𝑛 (𝑥𝑥). (1) For upward criteria, 𝑛 ′(𝑥𝑥) should be non-negative. Because when an upward criterion increases, the least we can expect is that utility obtained from it does not change. (2) Before 𝑥𝑥𝛼𝛼, which is set based on the application, utility is zero. (3) From 𝑥𝑥𝛼𝛼 to 𝑥𝑥𝑚𝑚, 𝑛 “(𝑥𝑥)≥0. In this interval utility increases rapidly. (4) Utility in 𝑥𝑥𝑚𝑚 is set to 0.5. (5) From 𝑥𝑥𝑚𝑚 to 𝑥𝑥𝛽𝛽, 𝑛 “(𝑥𝑥)≤0. In this interval utility increase with slower pace. (6) Utility for values of 𝑥𝑥 higher than 𝑥𝑥𝛽𝛽 is set to one. 𝑛 (𝑥𝑥)=⎩⎪⎪⎨⎪⎪⎧0 𝑥𝑥<𝑥𝑥𝛼𝛼ô‰€ð‘¥ð‘¥âˆ’𝑥𝑥𝛼𝛼𝑥𝑥𝑚𝑚−𝑥𝑥𝛼𝛼ô‰ðœðœ1+ô‰€ð‘¥ð‘¥âˆ’𝑥𝑥𝛼𝛼𝑥𝑥𝑚𝑚−𝑥𝑥𝛼𝛼ô‰ðœðœ 𝑥𝑥𝛼𝛼≤𝑥𝑥≤𝑥𝑥𝑚𝑚 𝑏𝑏−𝑒 −𝑎𝑎(𝑥𝑥−𝑥𝑥𝑏𝑏) 𝑥𝑥𝑚𝑚≤𝑥𝑥≤ 𝑥𝑥𝛽𝛽1 𝑥𝑥>𝑥𝑥𝛽𝛽 (2)

𝑛

(𝑥𝑥) is shown in Figure 1. 𝑥𝑥𝛼𝛼, 𝑥𝑥𝑚𝑚 and 𝑥𝑥𝛽𝛽 control the beginning, middle and end points respectively. 𝜁𝜁 and a control the convexity and concavity of the two sides of 𝑥𝑥𝑚𝑚. With these 5 degrees of freedom, any parameter of any traffic type or user

preference can be normalized elastically. In order for the assumptions to be true all the time, c, b and 𝑥𝑥𝑏𝑏 should be as follows: ⎩⎪⎪⎨⎪⎪⎧𝑐 =

𝑒 −

𝑎𝑎􀵫𝑥𝑥𝛽𝛽−

𝑥𝑥𝑚𝑚􀵯,

𝑎 >

𝑏𝑏=12𝑐 −

1

𝑐 −1𝑥𝑥𝑏𝑏=𝑥𝑥𝑚𝑚+ln􁉀𝑏𝑏−12􁉁𝑎 (3)

Since normalization function used for downward criteria should have opposite characteristics, 𝑛 𝑑(𝑥𝑥) is used for these kind of attributes which is defined as: 𝑛 𝑑𝑑(𝑥𝑥)=1−𝑛 (𝑥𝑥) (4)

B. Proposed ELECTRE II based network selection method

Most of prior MADM algorithms express 𝑥𝑥ð‘-ð‘-ð‘-ð‘- in (1) as a crisp number which is not suitable for network selection problem. Some of wireless network parameters like throughput are varying over even a short period of time. Assigning a crisp number to express the performance of attributes is not a realistic modeling, instead we use a vector with variable length. 𝑋𝑋𝑛𝑛ð‘-ð‘-ô€µ«ð´ð´ð‘-ð‘-ô€µ¯={𝑎 |𝑎 ∈ 𝑋𝑋𝑛𝑛ð‘-ð‘-ô€µ«ð´ð´ð‘-ð‘-ô€µ¯,0≤𝑎 ≤1} is the vector used instead of 𝑥𝑥ð‘-ð‘-ð‘-ð‘- which represents different measurements of attribute 𝐴𝐴ð‘- at different sampling times or different opinions of decision makers about the performance of network 𝑁𝑁ð‘-ð‘-.

In ELECTRE II method [13] a pair wise comparison between each pair of networks (𝑁𝑁𝑙𝑙,𝑁𝑘𝑘) divide the criteria into three general sets. The concordance set 𝐽𝐽𝐶𝐶={ð‘-ð‘-|𝐴𝐴ð‘- (𝑁𝑁𝐾𝐾)>𝐴𝐴ð‘- (𝑁𝑁𝑙𝑙)}, indicating all the criteria in which 𝑁𝑁𝐾𝐾 is better than 𝑁𝑁𝑙𝑙, the discordance set 𝐽𝐽𝐷𝐷={ð‘-ð‘-|𝐴𝐴ð‘- (𝑁𝑁𝐾𝐾)<𝐴𝐴ð‘- (𝑁𝑁𝑙𝑙)}, representing the criteria in which 𝑁𝑁𝐾𝐾 is worse than 𝑁𝑁𝑙𝑙 and finally indifference set 𝐽𝐽=={ð‘-ð‘-|𝐴𝐴ð‘- (𝑁𝑁𝐾𝐾)=𝐴𝐴ð‘- (𝑁𝑁𝑙𝑙)}, indicating all criteria in which there is no difference between 𝑁𝑁𝐾𝐾 and 𝑁𝑁𝑙𝑙. But this procedure can be used while elements of the decision matrix (X) are crisp numbers. As pointed out earlier each element of the decision matrix is a vector with variable length indicating different measurements or different opinions of decision makers about the performance of each criterion. In this context, we use the

Figure 1. n(x)

In order to show in our approach the probability of ranking abnormality occurrence is less than mentioned methods we considered 20 networks of different kinds with different characteristics (see table 4). To model the dynamic nature of wireless environment each attribute of networks changes randomly up to maximum 20 percent each 5 seconds and the amounts get updated. Users are divided into 4 groups with different traffic classes namely conversational, streaming, background and interactive. For each of these users the available networks are ranked at each time epoch and randomly 2 of these networks are eliminated and the ranking process repeats, if the ranking order is changed then ranking abnormality has happened. The simulation time was 1000 seconds and ranking abnormality probability is defined as the number of times that ranking abnormality happens to number of all times that ranking procedure has been done. The results were compared with TOPSIS, GRA and SAW (see Fig.3-6).

We can notice that ranking abnormality probability is less for background and interactive traffic compared to conversational and streaming traffic classes which is caused by the high sensitivity and unbalanced weight of some of the criteria in streaming and conversational traffic classes. Also overall probability is reduced using our proposed algorithm. Among GRA, TOPSIS and SAW methods, GRA has the least average ranking abnormality probability. Our proposed method has decreased this probability by 33%, 41%, 51%, 43% for conversational, streaming, interactive and background traffics respectively, compared to GRA.

B. Simulation 2

In order to measure the robustness of a ranking algorithm, sensitivity analysis is used. Value of attributes are changed for a specific amount and then the change in the scores of alternatives is measured. The less the changes are the more robust that algorithm is. We used the networks and user types in the last subsection and we changed the amount of attributes

much difference in sensitivity for different traffic classes in our proposed algorithm while SAW and TOPSIS algorithms are more traffic sensitive. Furthermore, our algorithms has decreased sensitivity by 54%, 41%, 36% and 35% for conversational, streaming, background and interactive traffic classes respectively, compared to TOPSIS and 41%, 37%, 23% and 25% compared to SAW algorithm.

Figure 5. Ranking abnormality for background traffic

Figure 6. Ranking abnormality for interactive traffic

Figure 7. Sensitivity analysis for TOPSIS, SAW and proposed algorithm

V.CONCLUSION

In this paper we investigated network selection in heterogeneous wireless networks. We discussed ranking abnormality, weak modeling of network performance, concept of tolerable compensation by different attributes and normalization as weak points of current MADM algorithms. We proposed a new way considering user needs and preferences for normalization of the criteria and a new algorithm based on ELECTRE II and fuzzy evaluation of network performance for the decision phase. Simulation were performed to evaluate the proposed procedure for network selection. Results show [35%-54%] decrease in sensitivity compared to TOPSIS and [23%-41%] decrease compared to SAW. Ranking abnormality was decreased by [33%-51%] compared to GRA which has the best performance among current methods.

REFERENCES

[1] Wang, Lusheng, and G-SGS Kuo. “Mathematical modeling for network selection in heterogeneous wireless networks-A tutorial.” Communications Surveys & Tutorials, IEEE 15.1 (2013): 271-292.

[2] Gelabert X, Sallent O, Prez-Romero J, Agust R. Performance evaluation of radio access selection strategies in constrained multi-access/multi-service wireless networks. Computer Networks 2011; 55(1):173-192.

[3] Verma R, Singh N. GRA based network selection in heterogeneous wireless networks. Wireless Personal Communications 2013; 72(2):1437-1452..

[4] Lahby M, Leghris C, Adib A. New multi access selection method based on mahalanobis distance. Applied Mathematical Sciences 2012; 6(53-56):2745-2760

[5] Lassoued I, Bonnin J-M, Ben Hamouda Z, Belghith A. A methodology for evaluating vertical handoff decision mechanisms. 7th International Conference on Networking, ICN 2008, Cancun, Mexico, 2008; 377-384.

[6] Chamodrakas, Ioannis, and Drakoulis Martakos. “A utility-based fuzzy TOPSIS method for energy efficient network selection in heterogeneous wireless networks.” Applied Soft Computing 12.7 (2012): 1929-1938.

[7] Shi Z, Zhu Q. Network selection based on multiple attribute decision making and group decision making for heterogeneous wireless networks. The Journal of China Universities of Posts and Telecommunications 2012; 19(5):92-114

[8] P. Coucheney, C. Touati, and B. Gaujal, “Fair and efficient user-network association algorithm for multi-technology wireless networks,” in Proc.IEEE Conf. INFOCOM, Apr. 2009, pp. 2811-2815.

[9] W. Zhang, “Handover decision using fuzzy MADM in heterogeneous networks,” in Proc. IEEE WCNC, Mar. 2004, pp. 653-658.

[10] O. Falowo and H. Chan, “RAT selection for multiple calls in heterogeneous wireless networks using modified topsis group decisionmaking technique,” in Proc. IEEE Int. Symp. PIMRC, Sep. 2011, pp. 1371-1375.

[11] E. Aryafar, A. Keshavarz-Haddad, M. Wang, and M. Chiang, “RAT selection games in HetNets,” in Proc. IEEE Conf. INFOCOM, Apr. 2013,pp. 998-1006.

[12] IEEE Standard for Local and metropolitan area networks- Part 21:Media Independent Handover

[13] Duckstein, Lucien, and Mark Gershon. “Multicriterion analysis of a vegetation management problem using ELECTRE