Comparison of queue length and delay of three models ().
To solve the problem of multi-priority and multi-business tasks in wireless sensor networks, a two-level polling control system is proposed based on the basic polling system. The system divides the sites into ordinary sites and high-priority site according to business priorities. The ordinary sites use gated services, and the high-priority sites use exhaustive services. The mathematical model of the system is established by using the method of Markov chain and probability generating function, and the important parameters such as query period, throughput, average queue length and average delay are obtained. The simulation results are approximately equal to the theoretical calculation results, which shows that the theoretical analysis method is correct and effective. While distinguishing priority services, the system ensures the delay of users and improves the quality of service of the polling system.
- polling system
- average queue length
- average waiting delay
- priority control
With the rapid development of science and technology, human beings have been in the information age, and sensor technology, as the most important and basic technology of information acquisition, has also been greatly developed. Wireless sensor networks (WSNs) are a new generation of sensor network and the core of Internet of things technology . It is an interdisciplinary research field involving sensor technology, computer network technology, wireless transmission technology, embedded computing technology, distributed information processing technology, microelectronic manufacturing technology, software programming technology and so on . Through a variety of information sensors, it collects all kinds of needed information in real time, and realizes the functions of monitoring and management through the access of the Internet. In this process, the mode of data transmission must be considered. MAC protocol specifies the way that nodes occupy wireless channels when transmitting data. It reduces transmission delay and improves network throughput and service quality through communication protocol and mechanism. Therefore, the performance of MAC protocol determines the data transmission capability of WSNs .
MAC protocol based on polling access is a non-competitive control method, which allocates fixed channel resources to users . In the process of data communication, the users who get the transmission right exclusively enjoy the allocated channel resources, so that the network can realize the conflict-free transmission of information. Due to its unique conflict-free transmission mode, polling-based MAC protocol has always been a hot topic in WSNs research [5, 6]. With the development of research, its service mode has been continuously expanded [7, 8, 9]. Kunikawa and Yomo proposed a polling MAC protocol based on EH-WSN, which improves the throughput of WSNs nodes . Adan and his collaborators proposed a dual-queue polling model, and then analyzed the equilibrium distribution of the system by using the compensation method and a reduction to a boundary value problem respectively . Abidini et al. studied the vacation queuing model and the single-server multi-queue polling model . The polling system is mainly divided into three categories: gated, exhaustive and limited according to the service strategy . Researchers have been studying all kinds of polling systems focusing on the optimization and improvement of system performance . With the rapid development of modern network technology, a single service strategy has been unable to meet the needs, such as priority business and multi-business tasks. Therefore, it is necessary to make comprehensive use of various service strategies, but at this time the difficulty of system analysis is greatly increased. Yang and Ding analyzed the polling system with mixed service, but did not give an accurate analysis of the second-order characteristics of the system .
Herein, we first analyze the three basic polling systems, and then propose a two-level polling system model with exhaustive service in the central site and gated service in the ordinary sites, which not only solves the problem of differentiated priority business, but also ensures the delay of the system. Then the E(x) characteristics of the system such as average queue length, average query cycle and throughput are analyzed. Finally, the performance of the system is verified by simulation experiments.
2. Three basic polling system models
The basic model of the polling system consists of a logical server (relay site) and N sites. The server queries each site to provide services according to the predetermined service rules. The performance of the polling system is usually determined by the order of querying each site, the service policy of the site and the service order of information packets within the site. The system model is shown in Figure 1. When the system is running, the polling order is as follows: at time, the server provides services for site i; after the service is completed, the server provides services for site i + 1 at time.
2.1 Exhaustive service polling system
The exhaustive service system is when the server starts to serve the site, it not only transmits the previously arrived information packets in the site, but also transmits the newly arrived information packets during the service period. Its probability generating function at time is:
where represents the probability generating function of the random variable of the time required for the server to provide exhaustive service to the information packets entering any site in any time slot.
2.1.1 Average queue length
The average queue length of the system is defined as the average number of packets stored in the site j when the ordinary i starts to receive service at time, expressed by . Definition:
2.1.2 Average waiting delay
The average waiting time of the system is the time it takes for a packet to enter the site until it is sent out, expressed by . Define the joint moment of random variable as .
2.2 Gated service polling system
The gated service polling system means that when the server queries the site, it only provides services for the packets that currently arrive at the site, and the packets arriving in the service process will not provide services until the next round of access of the server. The definitions of average queue length and average waiting delay of gated service polling system are similar to that of exhaustive service polling system, and its probability generating function at time is:
2.2.1 Average queue length
2.3 Limited service polling system
In the polling system with limited service, it is assumed that there are N terminal stations in the system, and the N terminal stations are queried by a server in turn. The server only serves one packet when polling each terminal station, and the rest of the packets is queued with the newly arrived packets to be sent in the next cycle with the same service rules. The average queue length and average delay of the limited service polling system are also consistent with those of the exhaustive service polling system, and its probability generating function at time is:
2.3.1 Average queue length
2.4 Performance comparison of three polling systems
The above analysis method of embedded Markov chain and probability generating function are used to obtain the accurate expressions of the average queue length and average waiting time of three different service strategies, i.e., exhaustive, gated and limited service polling systems. In this section, the performance characteristics of three different service strategy polling systems are compared by setting the working conditions and operating parameters of the system. The system meets the following conditions:
The parameters of each station obey the same distribution law, i.e., the distribution is symmetric.
Arrival time, query conversion time, and waiting time for service are all measured in time slots.
The number of packets arriving at any time slot at each station obeys the Poisson distribution.
The polling systems with three different service strategies all satisfy the steady-state condition .
It can be seen from Figures 2 and 3, the performance indicators of the polling systems with three different service policies, i.e., the average queue length and the average waiting delay are different. The average queue length of the exhaustive service polling system is the smallest, the gated service polling system takes the second place, and the average queue length of the limited service polling system is the largest, and the average waiting delay also satisfies the same law. From the perspective of fairness, on the contrary, the fairness of the limited service polling system is the best, while that of the exhaustive service polling system is the worst. The polling systems with three different service strategies have their own characteristics and advantages. In the actual situation, the appropriate polling service strategy should be selected according to the scope of application and application conditions to meet different application needs. When the system requires high fairness, select the limited service strategy; when the system requires high real-time performance, choose the exhaustive service strategy; when the system requires both real-time and fairness, choose the gated service strategy.
3. Exhaustive-gated two-level polling system
Based on the basic polling system and the requirements of different priority business in WSNs, an exhaustive-gated two-level polling access control strategy is proposed. The principle of the exhaustive-gated service two-level control polling system is as follows: the polling system is composed of N ordinary sites and a central site h. The server serves the central site according to the exhaustive service rule and the ordinary sites according to the gated service rule. The system model is shown in Figure 4. After the polling starts, the server first provides exhaustive service to the central site, i.e., the information arrived before the start of the service and the information arrived during the service until the site is empty, and then go to query the ordinary sites. If the ordinary site i is not empty, the server will serve it according to the gated service rule. When the service of the site i is finished, it will turn to query the central site h. After the central site completes the prescribed service, it starts to serve the ordinary site i + 1 again. The exhaustive-gated two-level control polling system distinguishes between the central site and the ordinary sites by always giving priority to the central site, and the service of the central site is guaranteed first.
We use the methods of stochastic process and probability generating function to analyze the performance of the system. The random variable is defined as the number of information packets queued for service in the memory of the site i at the time. is the number of information packets queued for service in the memory of the central station at time. The state variable of the whole system at time is ; at time, the state of the system is . At time, the state of the whole system can be expressed as . Then the N + 1 states of the system constitute a Markov chain, which is aperiodic and ergodic.
3.1 Definition of variables
In any time slot, the process of information packets arriving at each station is subject to the independent and identically distributed Poisson process, and the probability generating function and mean value of its distribution in ordinary stations are and respectively. The probability generating function and mean value of the distribution of at the center site are and respectively.
The service time of an information packet of any site is subject to independent and identically distributed probability distribution. In the ordinary sites, the probability generating function, mean value and second-order origin moment of the distribution are , and respectively. The probability generating function, mean value and second order origin moment of the distribution at the center station are , and respectively.
After any ordinary station completes transmission service, the transfer time to the query center site is subject to an independent and identically distributed probability distribution, whose probability generating function, mean value and second-order origin moment are , and respectively. When the central site is converted to the ordinary site, the parallel control strategy is adopted, i.e., the server queries the next ordinary site that needs service while serving the central site, which saves the conversion time and improves the service efficiency of the system.
Define the following variables:
: the time when the server moved from the ordinary site i to the central site.
: the service time for the server to provide gated service to the ordinary site i.
: the service time for the server to provide exhaustive service to the central site h.
: the number of information packets entering the central site within time.
: the number of information packets entering the central site within time.
: the number of information packets entering site i within time.
: the number of information packets entering site j within time.
: the number of information packets entering site j within time.
According to the principle of the model, the state variables of the system at each time satisfy the following relations:
3.2 Probability generating function
Assuming that the storage capacity of each ordinary site and the central site is large enough, the information packets will not be lost, and the information packets will be served in the order of first-come-first-served. The system reaches a steady state under the condition of , and the probability generating function in the steady state is defined as:
The probability generating function of the system serving the ordinary site i + 1 at time is as follows:
3.3 Average queue length
Definition: The average queue length of the system is the average packets stored in node j when node i receives service at time.
The average queue length of the central station is:
When , the system is symmetrical and the average queue length of the ordinary site and the central site is respectively:
3.4 Average cycle
The average cycle of the polling system is expressed as the time interval between two consecutive visits to the same queue by the server, which is the statistical average of the time taken by the server to serve N + 1 sites according to the prescribed service rules. The calculation is as follows:
3.5 Second-order characteristics
The joint moment of central site random variable is defined as , and the joint moment of ordinary site random variable is defined as , which is obtained by the property of probability generating function.
When the system is symmetrical:
3.6 Average waiting delay
Definition: The average delay of the polling system is the time it takes for an information packet to arrive at the site until the information packet is sent. According to the approximate expressions of and calculated above, the average waiting delay can be obtained by substituting the following two expressions respectively.
The average waiting time for ordinary site is:
The average waiting time at the central site is:
4. Experimental analysis
Based on the above two-level priority polling service model, theoretical value calculation and experimental simulation are carried out according to the following working conditions.
The data communication process is ideal and the data will not be lost.
The data entering each station in any time slot satisfies the Poisson distribution.
The polling system satisfies .
4.1 Symmetrical two-level polling system
Figures 5 and 6 show the change of average queue length and average waiting delay between the ordinary station and the central station with the arrival rate. It can be seen from the Figures that when the arrival rate is increasing, the average queue length and average waiting delay of information packets also increase. The queue length and delay of central station are much smaller than those of ordinary sites, which indicates that the model has strong ability to distinguish business.
Figures 7 and 8 show the comparison between the average queue length and the average waiting delay of the exhaustive-gated two-level polling system and the single-level gated polling system. It can be seen that in the case of the same network size, the queue length and delay of the two-level model are less than that of the single-level model. It shows that the model not only distinguishes different priority business, but also optimizes the queue length and delay of ordinary sites, and improves the quality of service of the polling system.
4.2 Asymmetric two-level polling system
In WSNs, different stations handle different business, and the arrival rate of information packets, service time and polling conversion time are also different. To distinguish the business of different sites, an asymmetric two-level polling system is used to provide services. The performance analysis of the asymmetric system is shown below.
As can be seen in Figures 9 and 10, the average queue length of the ordinary sites and the central site is obviously affected by the service time, and the queue length increases with the service time. Similarly, the average queue length of the two stations with different priorities has a great difference, which shows that the priority of the polling system is well distinguished. In addition, the growth rate of the average queue length of the central station of 1 to h and 2 to h is relatively small compared with other sites. The main reason is that the arrival rate of each queue is different, which is consistent with the theoretical analysis. It can be seen from Eq. (19) that the queue length of the central station is directly proportional to the arrival rate, so when the arrival rate of the two stations is small, the impact on the queue length of the central station is small.
As can be seen from Figures 11 and 12, when the number of cycles selected is large, the theoretical value of the average waiting time is consistent with the experimental value. For the same system, when the service time of the system increases, the average waiting time also increases accordingly. In the case of the same load, the average waiting time of the central site is less than that of the ordinary sites, which indicates that it is effective to distinguish the business priority by using the mixed polling service mode. The performance of the system has been optimized as a whole.
Table 1 shows the comparison of the average queue length and average delay (ordinary sites) between different models and the model proposed in this chapter, where the system is assumed to be symmetrical. It can be seen that whether compared with the single-level models or the other two-level models, the average queue length and delay of users in this model are smaller. It shows that the model proposed in this chapter not only distinguishes different priority business, but also has better performance.
|Arrival rate (λ)||Single-level gated||Single-level exhaustive||The model of literature ||Two levels of exhaustive-gated|
In this book chapter, we adopt a prioritized polling system which combines exhaustive service with gated service, i.e., gated service is used in ordinary sites with low priority, and exhaustive service is used at central sites with high priority. Then a two-level priority service model is constructed by using the service mechanism of parallel pattern. The average queue length and average waiting delay of the service model are accurately analyzed by using embedded Markov chain and probability generating function, and verified by simulation experiments. The results show that the system can distinguish the business with different priorities, the average queue length and average waiting delay of users are lower, and the quality of service of the system is higher.
This work was supported by the National Natural Science Foundation of China under Grant No. 61461054 and No. 61461053.