A quality-of-service evaluation method based on the cloud model for routing protocols in wireless sensor network

Abstract

The routing layer quality of service in wireless sensor network depends on different indices such as throughput, delay, packet loss rate, energy consumption, and degree of congestion. A single index does not adequately reflect the real quality of service while an excessive number of indices increase the complexity of the evaluation model. In addition, existing quantitative evaluation methods can lead to under-fitting or over-fitting. In this article, we present a comprehensive qualitative quality-of-service evaluation method based on the cloud model. Using Gaussian cloud transformation, each quality-of-service index can be divided into several qualitative concepts (cloud models). Concepts belonging to different indices can be combined together to evaluate the quality of service. We use a frequent-pattern tree approach to mine association rules of quality-of-service concepts and arrive at a suitable decision. This method simplifies the evaluation model by transforming a numeric value to its equivalent qualitative concept and brings out the internal relationships among different quality-of-service indices according to the association rules. Besides, it automatically finds a common standard to evaluate and compare different routing protocols simultaneously. The evaluation results show that the proposed method provides a good quality-of-service assessment when applied to different routing protocols.

Keywords

Wireless sensor network cloud model quality-of-service evaluation quality-of-service concepts divide association rules mining

Introduction

Over the past decade, there have been several advancements in wireless sensor network (WSN) research. An important aspect, the quality of service (QoS), depends on various key parameters, such as the loss rate, latency, lifetime, and throughput, and determines the performance of multiple layers.^1,2 There are few studies that focus on QoS performance of different protocols for routing evaluation. However, the deployment scenario in WSN is complex and application-specific, making it difficult to evaluate the QoS using traditional methods. Most QoS evaluation techniques on routing protocols concentrate on some specific parameters. Typical examples include the communication reliability, topology robustness, network convergence, and energy consumption. Because of the differences among routing protocols, a comprehensive evaluation would need an excessive number of QoS indices.

In general, every routing protocol has a specific goal, and so the evaluation method is different for each. For a single protocol, the performance is compared by varying the protocol index, network scale, or protocol variety.³ When there are many protocols, a horizontal comparison for more than one parameter can be performed.^4,5 These evaluation methods concentrate on a specific single index and lack the ability to provide a comprehensive evaluation based on multiple indices. Moreover, because of the differences between the routing protocols, it is hard to create a unified model to describe and compare some common parameters. This makes the comparison of the protocols rigid, and the deep relationship between performance indices is not evident. In this article, we design a novel QoS evaluation method for routing protocols based on the cloud model. This method transforms a quantitative expression into its qualitative equivalent and provides a comprehensive evaluation of different protocols. The cloud model is a fuzzy concept that utilizes a mathematical model to represent the possibility that a quantitative expression belongs to a specific qualitative concept.⁶ By transforming QoS indices into cloud models, we can divide an index into several concepts and mix different indices by association rule mining. Figure 1 shows the evaluation process using the cloud model and association rule mining. The association rule mining is a frequent-pattern tree (FP-tree)⁷ algorithm which generates a set of QoS remarks (association rule set) with desired parameters. The FP-tree represents the internal relationships between the QoS indices and improves the reliability of the evaluation result.

Figure 1.

QoS evaluation process based on the cloud model.

The rest of the article is organized as follows. In section “Cloud model and QoS evaluation,” we describe the basic procedure of QoS evaluation and the method based on the cloud model. Section “Division of QoS indices parameters” describes the division algorithm of QoS indices. Section “Association rule mining based on FP-tree” describes the association rule mining algorithm for QoS indices. Section “Design and analysis of the experiments” presents experimental results of concepts division and QoS evaluation. Section “Discussion” discusses some arguments and questions. Finally, the conclusions are presented in section “Conclusion.”

Cloud model and QoS evaluation

Cloud model description

The cloud model reflects the bidirectional transformation process between a qualitative concept and its quantitative expression. Let $U$ represent the domain under consideration that is expressed by numeric values. Let $C$ be a qualitative concept. If $x \in U$ is a stochastic implementation of $C$ and the certainty $μ (x) \in [0, 1]$ of $C$ is a random number with a stable trend, then the distribution of $x$ on $U$ is called a cloud and every $x$ is called a drop.⁸ It is hard to provide an accurate mathematical expression for a qualitative concept defined using natural language because of randomness and fuzziness. The cloud model is based on the linguistic value of natural language. It gives a quantization method for a qualitative concept using which the model can maintain the randomness and fuzziness of concepts.

A typical cloud model uses the expected value $Ex$ , the entropy $En$ , and the hyper entropy $He$ to express a qualitative concept. $Ex$ represents the central value of a concept on the domain space. $En$ represents the discrete degree or uncertainty measurement of the concept. $He$ is the uncertainty measurement of $En$ . In general, parameters of a cloud model depend on the distribution of statistical samples. For a specific index, there can be various cloud models that can describe the corresponding qualitative concept, such as the linear cloud model, the Gaussian cloud model, and the trapezium cloud model.⁹ The Gaussian distribution is an important probability distribution extensively used in different research approaches and applications. Therefore, the Gaussian cloud, based on the Gaussian distribution, is one of the most important and widely applied cloud models. In this work, we use a Gaussian cloud based on the Gaussian distribution and the Gaussian mixture model (GMM) to divide QoS concepts.

QoS evaluation based on the cloud model

There is always an uncertainty associated with realistic networks because of the dynamic characteristics of the routing layer. This is reflected in the fluctuation of the QoS attribute values at different time or scenes. However, it is difficult to analyze excess QoS data. The quick changes in QoS performance do not allow for an accurate evaluation of the WSN. Sometimes, the optimal QoS performance values, such as the speed or efficiency, are not the best choice for evaluating applications in comparison with parameters like stability or survivability.^10,11 In addition, existing evaluation methods that depend on a single parameter to describe the entire network are susceptible to issues like under-fitting and over-fitting. In such cases, the evaluation result is likely to misrepresent the present situation. Although these characteristics are hard to obtain and describe, a cloud model can convert quantitative QoS data to qualitative concepts. This simplifies the evaluation process, and the results are capable of reflecting the fuzziness of the WSN. Numerical characteristics $C (Ex, En, He)$ describe the fluctuation of an index. At the routing layer, the evaluation results and consequently the performance are impacted by several factors like the fast changing topologies and protocols. Therefore, it is necessary to maintain these internal relationships by transforming QoS indices into cloud models.

Division of QoS indices parameters

Confusion degree

The WSN is subject to uncertainties just like other wireless networks. This might cause the model to deviate from the Gaussian distribution. To ensure that the division into concepts is clear-cut, a parameter called the confusion degree $(CD)$ is introduced into the model. This quantifies the degree of coupling between concepts. $CD$ can be calculated using the parameters of a cloud concept as shown in Li and Du¹²

C D = 3 H e / E n

$He = En / 3$ is a significant dividing line when the Gaussian cloud model is used to represent a cloud concept. If $0 < He < En / 3$ , 99.7% of the cloud drops are located in the desired region. If $He > En / 3$ , the cloud model will be excessively discrete and the cloud concept will not be clear. Figures 2 and 3 represent ( $He = En / 10$ and $He = En$ , respectively) different cloud models with different values of $He$ . When $He = En$ , we observe that there is no clear cloud model that represents the concept. So, we can use $CD = 3 He / En$ to describe the degree of deviation of a concept.

Figure 2.

$He = En / 10$ .

Figure 3.

$He = En$ .

Gaussian cloud transformation

There are two algorithms used to divide the data sample: the heuristic algorithm for Gaussian cloud transformation (H-GCT) and the self-adaptive algorithm for Gaussian cloud transformation (S-GCT).¹³ H-GCT needs to determine the number of concepts before division as opposed to S-GCT. To avoid manual selection of the concept count, we use S-GCT to find all suitable cloud models and describe the definition of a specific cloud concept by $CD$ . The specifics of the two algorithms are described next.

Algorithm 1: H-GCT

Input: A sample set $X = {x_{i} | i = 1, 2, \dots, N}$ , Concept number M

Output:M Gaussian cloud models

Resolve $X$ into M Gaussian distributions using EM algorithm¹⁴

G (μ_{k}, σ_{k}), k = 1, 2, . . ., M

Compute the scale parameter $α$ using the following formulae

\begin{matrix} μ_{k - 1} + 3 α_{1} σ_{k - 1} = μ_{k} - 3 α_{1} σ_{k} \\ μ_{k} + 3 α_{2} σ_{k} = μ_{k + 1} - 3 α_{2} σ_{k + 1} \\ α = \min {α_{1}, α_{2}} \end{matrix}

Generate the parameters of the Gaussian cloud model

\begin{matrix} E x_{k} = μ_{k} \\ E n_{k} = (1 + α_{k}) σ_{k} / 2 \\ H e_{k} = (1 - α_{k}) σ_{k} / 6 \end{matrix}

Here, $α$ indicates the degree of overlap between two adjacent Gaussian distributions. A cloud model with a low value of $α$ results in a clearer concept. One index will be presented by only one cloud model hardly (in fact, there is no need to evaluate an index having only one level). So, we use the subscript index 1 to $k$ to distinguish cloud models with different evaluation level.

Algorithm 2: S-GCT

Input: A sample set $X = {x_{i} | i = 1, 2, \dots, N}$ , threshold $β$ of $CD$

Output:M Gaussian cloud models

Convert $X$ into a frequency histogram and find all the crest locations in the histogram. Set the number of crest locations as the initial value of $M$ .

Cluster $X$ into $M$ cloud models using H-GCT. The sample set $X$ and $M$ obtained in Step 1 are the input parameters for H-GCT

C (E x_{k}, E n_{k}, H e_{k}), k = 1, 2, \dots, M

Calculate the $CD$ of every cloud model. If $C D_{k} > β, k = 1, 2, \dots, M$ , then set $M = M - 1$ , and jump to Step 2, else output M Gaussian cloud models.

The threshold $β$ is a hyper-parameter of Algorithm 2 and indicates whether the cloud model is clear or not. A large value of $β$ indicates an efficient algorithm, but it results in numerous cloud models to divide the real data set.

In the execution phase, S-GCT will call H-GCT repeatedly to find appropriate cloud models (from Step 2 to Step 3 in S-GCT). The complexity of S-GCT depends on the sample set X and the required clarity of cloud models. If the I frequency histogram of X is smooth enough, the value of M will be less and close to correct. If an appropriate value of $β$ is given in S-GCT, the number of clustering process will decrease.

Association rule mining based on FP-tree

There are various algorithms like FP-tree that are suitable for mining frequent sets. These algorithms target different structures, scenarios, and performance requirements.¹⁵ In this section, we use FP-growth to find the final evaluation of QoS. This is an algorithm like FP-tree, has a simple structure, and is good for dense databases. An n-tuple consisting of different QoS indices is represented as a transaction in the FP-tree algorithm. Too many values on a specific index will lead to a dramatic increase in the size of the transaction database. The cloud transformation provides a way to map a set of quantitative data to a small amount of cloud concepts, reducing the complexity of the FP-tree algorithm. The data at the edge of a cloud model do not always fit in with the Gaussian distribution and presents some uncertainty; this partly reflects the randomness inherent to WSN.

When a new set of QoS data is obtained, the cloud models are used to map the data to a corresponding cloud concept by calculating the probability that the value belongs to a particular cloud model. For example, an n-tuple {580, 2.0, 92, 5.9} consisting of different QoS indices could be mapped to an n-tuple {medium, low, high, high} that can be set as a transaction in association rule mining. The cloud concepts of different QoS indices can be combined to generate a remark set about the QoS performance. By association rule mining, we can reject the unavailable evaluation remarks.¹⁶ used an a priori algorithm to obtain link quality remarks. However, this involved scanning the transaction database repeatedly. In this work, the FP-tree algorithm is applied to routing performance association rule mining. All frequent sets are compressed into an FP-tree, and the algorithm uses a recursion method to obtain the rules.

Algorithm 3: FP-growth

Input: A transaction set $T = {t_{i} | i = 1, 2, \dots, N}$ , the minimum support $δ$ of frequent patterns

Output: A frequent pattern set $Y = {y_{i} | i = 1, 2, \dots, M}$

Scan the transaction database and calculate the occurrence number of every transaction item. Delete the item if its minimum support is less than $δ$ and sort the remaining transaction items by the minimum support in descending order to get a new transaction set

F = {f_{i} | i = 1, 2, \dots, K}

Introduce $F$ into the Conditional Pattern Base (CPB) and create an empty suffix pattern $PostModel$ as the initial list containing frequent patterns.

Scan CPB and create an FP-tree by inserting every transaction item into the FP-tree.

Choose an unused item from the FP-tree and find all the paths from the root to the item. Add this item to $PostModel$ and delete it from all the paths. Output $PostModel$ along with its support as a frequent pattern.

Insert every path in Step 4 as a transaction item into a new CPB. If the new CPB is not empty, then jump to Step 3. Otherwise, go to Step 4.

Design and analysis of the experiments

In this section, we use different QoS parameters to evaluate a specific performance index. In certain circumstances, using different protocols can present greater diversity of performance as compared to a case using a specific protocol with various parameters. To find the most appropriate protocol, we compare Flooding, Directed Diffusion (DD),¹⁷ and the low-energy adaptive clustering hierarchy (LEACH) protocols¹⁸ using the same parameter. Experimental data are collected using a physical platform based on CC2530 and TinyOS.¹⁹

Classification of QoS cloud concepts

We use the energy consumption level (ECL), network transmission effects (NTE) (the acceptance rate of effective packets), and the degree of congestion (DoC) (the average data quantity of nodes at a certain time) to evaluate the average transmission delay (ATD), a key index of the routing layer. ECL, NTE, and DoC are set as the rule antecedent of the evaluation remarks, and ATD is set as the rule consequent. When the threshold of CD is set as $β = 0.5$ , ECL is divided into three concepts (low, medium, and high). Figure 4 shows the ECL data and a GMM of the initial result. Figure 5 shows the cloud models generated by S-GCT. Table 1 shows the parameters of all the cloud concepts. In the same way, we can divide NTE into 3 concepts (low, medium, and high), DoC into two concepts (low and high), and ATD into four concepts (extremely low, low, high, and extremely high). For the convenience of the association rule mining, concepts are numbered as ECL{A1, A2, A3}, NTE{B1, B2, B3}, DoC{C1, C2}, and ATD{D1, D2, D3, D4}.

Figure 4.

Result of GMM transformation on ECL.

Figure 5.

ECL concept cloud models.

Table 1.

Parameters of ECL cloud models.

Cloud concept	Ex	En	He	CD
Low	558	3.51	0.04	0.03
Medium	582	3.90	0.41	0.32
High	599	4.32	0.45	0.31

CD: confusion degree.

In association rule mining, we set the minimum support as $δ = 0.11$ and the confidence as 0.4. The algorithm of FP-tree obtains the eight strong association rules shown in Table 2. By analyzing the QoS indices of the rule antecedent, we can evaluate the current network delay situation. For example, $[A 2, B 1, C 2] \to D 4$ implies that when the ECL is medium, NTE is low, and DoC is high, the network delay is extremely high.

Table 2.

Association rules of cloud concepts.

ECL	NTE	DoC	ATD
A1	B2	C1	D1
A1	B2	C2	D1
A3	B2	C1	D2
A2	B1	C1	D2
A3	B3	C1	D2
A3	B1	C2	D3
A3	B2	C2	D3
A2	B1	C2	D4

ECL: energy consumption level; NTE: network transmission effects; DoC: degree of congestion; ATD: average transmission delay.

QoS index evaluation

The association rules generated by this method can be used to evaluate the performance of different routing protocols. By dividing QoS data into cloud models and choosing the corresponding rule antecedent, we can get the ATD evaluation presented by the association rule. In this experiment, we evaluated the ATD of Flooding, DD, and LEACH. Figure 6 shows the ATD numerical data of these protocols and their cloud concept. The LEACH protocol had the lowest ATD (the concept is “extremely low”) when compared to the Flooding and DD protocols. The Flooding protocol had the least stability and with an evaluation between the concept “high” and “extremely high.”

Figure 6.

Experimental ATD results. Three concepts are presented by the Gaussian cloud model to evaluate different protocols.

The QoS is affected by more than one factor, and it is difficult to find the most important factor or relationship among them. The evaluation of a specific QoS index can be simulated using other related indices. Therefore, we evaluate different QoS indices by changing the association rule mining target. Figure 7 presents the evaluation of DoC in the same situation (DoC is set as the rule consequent). In this experiment, the DD and LEACH protocols are evaluated as having a “low” DoC. The Flooding protocol spans the two concepts, which shows that it is unstable as compared to the other protocols. Because of the instability of the wireless environment, a protocol will exhibit a higher discreteness on DoC. However, it is still clear that all DoC samples can be divided into two concepts using the evaluation method.

Figure 7.

Experimental DoC results.

Discussion

Gaussian clouds can provide an extensive description and concept division for most scenarios and protocols. However, there are some QoS indices whose distribution is erratic or coverage is big, such as the DoC concept “low” in Figure 7. In this case, a Gaussian cloud model will deviate from the realistic distribution of data samples and the points located at the edge of a concept could be divided incorrectly. Although GMM can generate enough Gaussian cloud models to fit the data, an excessive number of concepts will make the association rule mining and evaluation complex. Therefore, the task of deciding the optimal distribution and cloud model requires more analysis. It might also be advisable to divide a QoS index with different cloud distributions.

In order to ensure that the evaluation reflects the real-time network performance, different association rules must be activated depending on the dynamic QoS parameters. In such a complex scenario, the parameters could change beyond the coverage range of cloud models. There could be some unknown rule antecedents, in which case the algorithm will not be able to find a correct association rule. In our future work, we will try to solve this problem by improving the granularity of the cloud concept division and enhancing the transaction database. Furthermore, some useful features, such as network topology and node number, in WSN can be set as other indices to find the influence related to routing protocols.

Conclusion

In this work, we proposed an evaluation method based on the cloud model to analyze and compare the performance of different routing protocols. The S-GCT algorithm was used to create Gaussian cloud models. An FP-tree (FP-growth) algorithm was used to perform association rule mining, which reduced the I/O and memory overhead. Compared to other methods that only provide the numerical results associated with a single QoS index, the proposed method provided a comprehensive evaluation of the different routing protocols. Also, The rule antecedent and consequent values were changed for different evaluation demands to facilitate the generation of the corresponding evaluation remark.

Footnotes

Academic Editor: Stefano Avallone

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work was supported by the Natural Science Foundation of Fujian Province of China under grant no. 2017J01776, the Science and Technology Plan Key Project of Fujian Province of China under grant no. 2014H0030, the Special Scientific Research Project of Provincial Colleges and Universities of Fujian Province of China under grant no. JK2015037, and the Young Dr Project of Quanzhou Normal University under grant no. 2015QBKJ02.

References

Said

. Performance evaluation of WSN management system for QoS guarantee. EURASIP J Wirel Comm 2015; 2015(1): 1–18.

Senouci

Mellouk

Senouci

et al . Performance evaluation of network lifetime spatial-temporal distribution for WSN routing protocols (Special issue: intelligent algorithms for data-centric sensor networks). J Netw Comput Appl 2012; 35(4): 1317–1328.

Alazzawi

Elkateeb

. Performance evaluation of the WSN routing protocols scalability. J Comput Syst Netw Commun 2008; 2008(1): 481046.

Mujica

Portilla

Riesgo

. Performance evaluation of an AODV-based routing protocol implementation by using a novel in-field WSN diagnosis tool. Microprocess Microsy 2015; 39(8): 920–938.

Zhu

. Genetic algorithm for energy-efficient QoS multicast routing. IEEE Commun Lett 2013; 17(1): 31–34.

Liu

Gan

. A new cognitive model: cloud model. Int J Intell Syst 2009; 24(3): 357–375.

Han

Pei

Yin

et al . Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Min Knowl Disc 2015; 8(1): 53–87.

Liu

. Study on the universality of the normal cloud model. Chinese Eng Sci 2004; 6(8): 28–34.

Wang

et al . Atanassov’s interval-valued intuitionistic linguistic multicriteria group decision-making method based on the trapezium cloud model. IEEE T Fuzzy Syst 2015; 23(3): 542–554.

10.

Wang

S-G

Sun

Q-B

Zhang

G-W

et al . Uncertain QoS-aware skyline service selection based on cloud model. Ruan Jian Xue Bao/J Softw 2012; 23(6): 1397–1412.

11.

Jiang

Cheng

. Optimization and quantitative evaluation mechanism of energy efficiency model on wireless sensor networks. Harbin Gongye Daxue Xuebao/J Harbin Inst Technol 2014; 46(5): 87–94.

12.

. Artificial intelligence with uncertainty. 2nd ed. Beijing, China: National Defense Industry Press, 2014.

13.

Liu

et al . Granular computing based on Gaussian cloud transformation. Fund Inform 2013; 127(1–4): 385–398.

14.

Bishop

. Pattern recognition and machine learning (Information science and statistics). New York: Springer-Verlag, Inc., 2006.

15.

Gupta

Garg

. FP-tree based algorithms analysis: FP-growth, COFI-tree and CT-PRO. Int J Comput Sci Eng 2011; 3(7): 2691–2699.

16.

Liu

L-L

X-L

Liu

et al . Cloud model-based link quality prediction model for wireless sensor networks. Ruan Jian Xue Bao/J Softw 2015; 26: 70–77.

17.

Intanagonwiwat

Govindan

Estrin

et al . Directed diffusion for wireless sensor networking. IEEE ACM T Network 2003; 11(1): 2–16.

18.

Heinzelman

Chandrakasan

Balakrishnan

. An application-specific protocol architecture for wireless microsensor networks. IEEE T Wirel Commun 2002; 1(4): 660–670.

19.

Tiny

, 2013, http://www.tinyos.net/

ECL	NTE	DoC	ATD
A1	B2	C1	D1
A1	B2	C2	D1
A3	B2	C1	D2
A2	B1	C1	D2
A3	B3	C1	D2
A3	B1	C2	D3
A3	B2	C2	D3
A2	B1	C2	D4

ECL	NTE	DoC	ATD
A1	B2	C1	D1
A1	B2	C2	D1
A3	B2	C1	D2
A2	B1	C1	D2
A3	B3	C1	D2
A3	B1	C2	D3
A3	B2	C2	D3
A2	B1	C2	D4

ECL	NTE	DoC	ATD
A1	B2	C1	D1
A1	B2	C2	D1
A3	B2	C1	D2
A2	B1	C1	D2
A3	B3	C1	D2
A3	B1	C2	D3
A3	B2	C2	D3
A2	B1	C2	D4