Game Theoretic Request Scheduling with Queue Priority in Video Sensor Networks

Abstract

Video sensor networks have been widely used to monitor environment and report abnormality. Each node collects video data, select a head node, and transmit the data to the head, and then the head reports the data to the base station. A head has to process both normal and abnormal data-reporting requests from its nearby nodes. To achieve QoS of surveillance, previous request scheduling methods minimize the data transmission delay or blocking rate but no comprehensive way was studied in the literature. In this paper, we propose a game strategic request scheduling based on a queue priority model in which a handover mechanism ensures that the abnormal requests are processed in time. In the game, video sensors select their heads to decide the arriving rates of both normal and abnormal requests; the heads decide the probability of handing over the abnormal requests. At the Nash Equilibrium Point (NEP), the normal data requesters optimize mean delay, the abnormal data requesters optimize mean blocking rate, and the heads balance the request load on them. Numerical analysis shows that the game strategic scheduling outperforms other scheduling methods that consider single objective (minimum delay or minimum blocking rate).

1. Introduction

Video sensor networks act as an efficient and reliable way to monitor environment and discover emergency or accidents [1, 2]. Each node of a sensor network collects video data and transmits the data to a nearby head, which is also a sensor and selected within a cluster. The head processes the data-reporting requests from members of the cluster and transmits the data to a sink node or a base station. The monitoring quality of service (QoS) of a video sensor network depends on how the data-reporting requests are scheduled and processed [2]. In order to collect data in time, a scheduling mechanism is supposed to optimize a metric of QoS (e.g., delay or blocking rate).

When executing the task of surveillance, a video sensor node can provide two types of service, one of which is to collect the data of normal video stream, and the other one is to collect the data of accident identification. Compared with the normal data, the abnormal data has a strict requirement of real time in order that the emergency and accidents can be discovered in time. A sensor node may transmit either normal or abnormal data to heads, which have to process both kinds of requests. Accordingly, a scheduling mechanism has to be designed to ensure that regular monitoring tasks are accomplished and accident reports are not delayed.

Previous request scheduling mechanisms focused on optimizing a single QoS metric (e.g., delay or blocking rate) without considering different QoS demands of two kinds of requests. Some work deals with packet queue management to improve the reporting delay and the video distortion [3]. Some other work pays too much attention to the occasionally accident data to avoid disturbing the regular monitoring tasks [4, 5]. A comprehensive way to achieve QoS of both kinds of reporting requests has not been studied in the literature. Such request scheduling problem entails a solution to optimize the utility of both the normal data-reporting requesters and abnormal data-reporting requesters. Game theory can be used where multiple participants interact with each other by their own strategies and pursue their respective optimal utility. When the participants arrive a Nash Equilibrium Point, they will not deviate from this solution because no more profit can be achieved by any of them [6, 7].

During the transmission of normal and abnormal data, there are totally three active participants: abnormal data-reporting requesters (ADR), normal data-reporting requesters (NDR), and cluster heads. They interact with each other. Both ADR and NDR have to choose the right heads to report their data because their choices will influence QoS of their monitoring tasks and the performance of the whole network. The cluster heads have to use cooperative way to optimize the cost and prolong the lifetime of the network. The three participants optimize their respective utility objective and converge to an equilibrium at which ADR and NDR make optimal head selection and heads use cooperation mechanism to lower and balance load on them.

In this paper, we propose a game theoretic request scheduling based on a handover mechanism between heads’ priority queues. ADR, NDR, and the heads act as three players in the game. NDR decides the head selection strategy to optimize mean request response delay. ADR selects their heads to optimize mean request blocking rate. The Cluster heads decide the handover strategy to optimize their load. We can get a Nash Equilibrium Point (NEP) at which each participant optimizes its own utility [6, 7]. Using NEP solution as the request scheduling, we satisfy the demand of service quality of both ADR and NDR as well as achieving load balance between heads. The main contributions of this paper include the following: $(1)$ we analyze the interaction among the three active participants in request scheduling game and aim to converge their respective behaviors (strategies) to an optimal equilibrium; $(2)$ from the view of data-reporting requesters, we use a comprehensive way to optimize utility of both kinds of data-reporting requesters rather than pay too much attention to a single QoS metric; $(3)$ from the view of cluster heads, we propose a handover mechanism between their request queue with priority in order to balance their respective load and prolong the lifetime.

The remainder of the paper is organized as follows. Related work is introduced in Section 2. In Section 3, we illustrate the network and QoS metrics. In Section 4 we propose the request scheduling game and the NEP solution. Some properties of NEP are validated in Section 5. Evaluation of the scheduling is shown in Section 6. Section 7 concludes the paper.

2. Related Work

In video sensor networks, abnormal data-reporting requests are usually given the high priority for accident discovery. In the paper [4], the authors propose an energy-aware packet scheduling algorithm to minimize the power consumption and prolong the lifetime of the whole video sensor network. In order to minimize the video distortion, they use a priority strategy to let the high priority packets to be transmitted over high bandwidth paths. Their proposed algorithm can constrain the energy consumption by selectively dropping the least important video packets. Durmus et al. propose an event-based fairness scheme for fair resource allocation of the involving events [3]. Their scheme is a queue management to improve the video distortion and the reporting latency. In the paper [5], the authors propose a periodic time scheduling to maximize the quality of monitoring of stochastic events. This scheduling has to decide the proportion of the time of event-monitoring and distribute a sensor's coverage time in order to achieve the proportion sharing and prolong the lifetime.

Cluster head or server selection schemes are studied in wired/wireless networks for efficient data transmission and QoS satisfaction [8–11]. Through redirection of a request dispatcher, distributed system assigns requests and balances loads on source servers. Much work pertains to system performance analysis with resource allocation method [12]. Different optimization schemes have been proposed to achieve QoS in data transmission [13–15].

Queue theory has been widely used in request scheduling [16]. In [12], the authors investigate price of anarchy of the distributed networks with multiple dispatchers. They model the request assignment by the dispatchers as a multiplayer noncooperative game, in which each dispatcher optimizes its own cost. Selfish server selection strategy of each dispatcher results in worse global cost of the whole network. Lower and upper boundaries of price of anarchy are given to illustrate that network performance degrades with increasing number of dispatchers. Authors in [17] study the job assignment problem in heterogeneous distributed server system. They propose an optimal static assignment to minimize the loads on the entire system. For the queue model, the author uses a scheduler to assign jobs (requests) to different servers. The scheduler is similar to the head selecting function in our request assignment game. This method can be deployed with handover mechanism to obtain global optimization of both normal and abnormal requests.

3. Priority Queue Model

3.1. Video Sensor Network Architecture

Cluster-based video sensor network architecture is composed of three types of nodes. As shown in Figure 1, each video sensor serves as a node to collect both normal and abnormal data from surrounding environment and transmits the data reports to their cluster heads. The head processes the data-reporting requests and transmits them to the sink node.

Figure 1

Video sensor network architecture.

3.2. QoS Metrics for Both ADR and NDR

To give the QoS metrics based on the video sensor network, we detail the queue model of handover mechanism between cluster heads.

Let $q_{jk}^{(i)}$ denote the probability that the head j hands over the abnormal data-reporting request to the head k at time i. This sharing policy satisfies ${\sum }_{k=\mathrm{1}}^n{q}_{jk}^{(i)}=\mathrm{1}$ for all the n heads. As shown in Figure 2, head 1 has a probability of   $q_{\mathrm{1}}$ to keep abnormal requests and $(\mathrm{1}-q_{\mathrm{1}})$ to hand over the requests to head 2. Head 2 has a probability of   $q_{\mathrm{2}}$ to keep abnormal requests and $(\mathrm{1}-q_{\mathrm{2}})$ to hand over the requests to sender 1. For each head, let $q_1$ denote the sharing policies of Head 1. As shown in Figure 2, $q_1$ represents the proportion of abnormal requests kept and processed by head 1, and $1-q_1$ represents the proporyion of abnormal requests handed over bye head 1. and let $P_{\mathrm{0}}$ denote the idle state probability of the head. As shown in Figure 2, we suppose that in the head 1's request processor the request arrival interval and the service time both obey exponential distribution. Then we let the normal request arrival rate be ${\lambda }_{\mathrm{1}}$ and the service rate ${\mu }_{\mathrm{1}}$ . The sharing policy for the two heads is $(q_{\mathrm{1}},q_{\mathrm{2}})$ . $q_{\mathrm{1}}$ means that in enough little interval the probability of keeping the abnormal requests in their own processor. $(\mathrm{1}-q_{\mathrm{2}})$ represents the probability of receiving requests from the other heads. Hence, the queuing rate of abnormal request packets in head 1 would be $q_{\mathrm{1}}{\beta }_{\mathrm{1}}+(\mathrm{1}-q_{\mathrm{2}}){\beta }_{\mathrm{2}}$ , while the arrival rates of both heads are ${\beta }_{\mathrm{1}}$ and ${\beta }_{\mathrm{2}}$ . Then we can construct the state transition differential equations. In the stable condition, the equations are expressed as follows:

$$\begin{array}{cc}& \left[{\lambda }_{\mathrm{1}}+q_{\mathrm{1}}{\beta }_{\mathrm{1}}+\left(\mathrm{1}-q_{\mathrm{2}}\right){\beta }_{\mathrm{2}}\right]P_{\mathrm{0}}={\mu }_{\mathrm{1}}{P}_{\mathrm{00}}\\ \left({\lambda }_{\mathrm{1}}+{\mu }_{\mathrm{1}}\right)P_{\mathrm{00}}=\left[{\lambda }_{\mathrm{1}}+q_{\mathrm{1}}{\beta }_{\mathrm{1}}+\left(\mathrm{1}-q_{\mathrm{2}}\right){\beta }_{\mathrm{2}}\right]P_{\mathrm{00}}+{\mu }_{\mathrm{1}}{P}_{\mathrm{10}},\\ \left({\lambda }_{\mathrm{1}}+{\mu }_{\mathrm{1}}\right)P_{s\mathrm{0}}={\lambda }_{\mathrm{1}}{P}_{s-\mathrm{1,0}}+{\mu }_{\mathrm{1}}{P}_{s+\mathrm{1,0}}\end{array}$$

(1)

with the constraint of $P_{\mathrm{0}}+{\sum }_{s=\mathrm{0}}^{\infty }‍P_{s\mathrm{0}}=\mathrm{1}$ .

Figure 2

Priority queue model with handover.

By solving the equations, we can get the state probabilities as follows:

$$\begin{array}{cc}& P_{\mathrm{0}}=\frac{{\mu }_{\mathrm{1}}-{\lambda }_{\mathrm{1}}}{{\mu }_{\mathrm{1}}+{\beta }_{\mathrm{2}}+q_{\mathrm{1}}{\beta }_{\mathrm{1}}-q_{\mathrm{2}}{\beta }_{\mathrm{2}}},\\ \begin{array}{c}{P}_{s\mathrm{0}}=\frac{{\lambda }_{\mathrm{1}}^s}{{\mu }_{\mathrm{1}}^{s+\mathrm{1}}}·\frac{\left({\mu }_{\mathrm{1}}-{\lambda }_{\mathrm{1}}\right)\left({\lambda }_{\mathrm{1}}+{\beta }_{\mathrm{2}}+q_{\mathrm{1}}{\beta }_{\mathrm{1}}-q_{\mathrm{2}}{\beta }_{\mathrm{2}}\right)}{{\mu }_{\mathrm{1}}+{\beta }_{\mathrm{2}}+q_{\mathrm{1}}{\beta }_{\mathrm{1}}-q_{\mathrm{2}}{\beta }_{\mathrm{2}}}\end{array}.\end{array}$$

(2)

For head 2, the state probabilities are expressed as follows:

$$\begin{array}{cc}& P_{\mathrm{0}}^{\prime }=\frac{{\mu }_{\mathrm{2}}-{\lambda }_{\mathrm{2}}}{{\mu }_{\mathrm{2}}+{\beta }_{\mathrm{1}}+q_{\mathrm{2}}{\beta }_{\mathrm{2}}-q_{\mathrm{1}}{\beta }_{\mathrm{1}}},\\ P_{s\mathrm{0}}^{\prime }=\frac{{\lambda }_{\mathrm{2}}^s}{{\mu }_{\mathrm{2}}^{s+\mathrm{1}}}·\frac{\left({\mu }_{\mathrm{2}}-{\lambda }_{\mathrm{2}}\right)\left({\lambda }_{\mathrm{2}}+{\beta }_{\mathrm{1}}+q_{\mathrm{2}}{\beta }_{\mathrm{2}}-q_{\mathrm{1}}{\beta }_{\mathrm{1}}\right)}{{\mu }_{\mathrm{2}}+{\beta }_{\mathrm{1}}+q_{\mathrm{2}}{\beta }_{\mathrm{2}}-q_{\mathrm{1}}{\beta }_{\mathrm{1}}}.\end{array}$$

(3)

3.2.1. Delay for Normal Requests

Let $D_{\mathrm{1}}^{(i)}$ and $D_{\mathrm{2}}^{(i)}$ denote the waiting time of normal request packets in head 1 and head 2. Based on the results above, we can get the expression of delay as follows:

$$\begin{array}{cc}& \begin{array}{c}{D}_{\mathrm{1}}^{\left(i\right)}=\frac{{\lambda }_{\mathrm{1}}^{\left(i\right)}+{\beta }_{\mathrm{2}}^{\left(i\right)}+q_{\mathrm{1}}^{\left(i\right)}{\beta }_{\mathrm{1}}^{\left(i\right)}-q_{\mathrm{2}}^{\left(i\right)}{\beta }_{\mathrm{2}}^{\left(i\right)}}{\left({\mu }_{\mathrm{1}}^{\left(i\right)}+{\beta }_{\mathrm{2}}^{\left(i\right)}+q_{\mathrm{1}}^{\left(i\right)}{\beta }_{\mathrm{1}}^{\left(i\right)}-q_{\mathrm{2}}^{\left(i\right)}{\beta }_{\mathrm{2}}^{\left(i\right)}\right)\left({\mu }_{\mathrm{1}}^{\left(i\right)}-{\lambda }_{\mathrm{1}}^{\left(i\right)}\right)},\end{array}\\ D_{\mathrm{2}}^{\left(i\right)}=\frac{{\lambda }_{\mathrm{2}}^{\left(i\right)}+{\beta }_{\mathrm{1}}^{\left(i\right)}+q_{\mathrm{2}}^{\left(i\right)}{\beta }_{\mathrm{2}}^{\left(i\right)}-q_{\mathrm{1}}^{\left(i\right)}{\beta }_{\mathrm{1}}^{\left(i\right)}}{\left({\mu }_{\mathrm{2}}^{\left(i\right)}+{\beta }_{\mathrm{1}}^{\left(i\right)}+q_{\mathrm{2}}^{\left(i\right)}{\beta }_{\mathrm{2}}^{\left(i\right)}-q_{\mathrm{1}}^{\left(i\right)}{\beta }_{\mathrm{1}}^{\left(i\right)}\right)\left({\mu }_{\mathrm{2}}^{\left(i\right)}-{\lambda }_{\mathrm{2}}^{\left(i\right)}\right)}.\end{array}$$

(4)

3.2.2. Blocking Rate for Abnormal Requests

Because the abnormal request packets can be regarded as the one processed by the cooperative heads, the blocking rate should be the average probability of abnormal requests being rejected by these heads. We use the sharing policy to figure out the condition probability.

As shown in Figure 2, the probability that a packet arrives at head 1 is expressed as $[\mathrm{1}-(\mathrm{1}-q_{\mathrm{1}}^{(i)})q_{\mathrm{2}}^{(i)}]$ . The probability that a packet arrives at head 2 is $[\mathrm{1}-(\mathrm{1}-q_{\mathrm{2}}^{(i)})q_{\mathrm{1}}^{(i)}]$ . The abnormal requests can be processed only when a head is idle. So the blocking rate $P_{c\mathrm{1}}^{(i)}$ for abnormal requests at head 1 is expressed as follows:

$$\begin{array}{cc}& P_{c\mathrm{1}}^{\left(i\right)}=\mathrm{1}-P_{\mathrm{0}}^{\left(i\right)}=\frac{{\lambda }_{\mathrm{1}}^{\left(i\right)}+{\beta }_{\mathrm{2}}^{\left(i\right)}+q_{\mathrm{1}}^{\left(i\right)}{\beta }_{\mathrm{1}}^{\left(i\right)}-q_{\mathrm{2}}^{\left(i\right)}{\beta }_{\mathrm{2}}^{\left(i\right)}}{{\mu }_{\mathrm{1}}^{\left(i\right)}+{\beta }_{\mathrm{2}}^{\left(i\right)}+q_{\mathrm{1}}^{\left(i\right)}{\beta }_{\mathrm{1}}^{\left(i\right)}-q_{\mathrm{2}}^{\left(i\right)}{\beta }_{\mathrm{2}}^{\left(i\right)}}.\end{array}$$

(5)

In the same way, we can get the blocking rate $P_{c\mathrm{2}}^{(i)}$ at head 2 as follows:

$$\begin{array}{cc}& P_{c\mathrm{2}}^{\left(i\right)}=\frac{{\lambda }_{\mathrm{2}}^{\left(i\right)}+{\beta }_{\mathrm{1}}^{\left(i\right)}+q_{\mathrm{2}}^{\left(i\right)}{\beta }_{\mathrm{2}}^{\left(i\right)}-q_{\mathrm{1}}^{\left(i\right)}{\beta }_{\mathrm{1}}^{\left(i\right)}}{{\mu }_{\mathrm{2}}^{\left(i\right)}+{\beta }_{\mathrm{1}}^{\left(i\right)}+q_{\mathrm{2}}^{\left(i\right)}{\beta }_{\mathrm{2}}^{\left(i\right)}-q_{\mathrm{1}}^{\left(i\right)}{\beta }_{\mathrm{1}}^{\left(i\right)}}.\end{array}$$

(6)

With condition probabilities, the total blocking rate $P_c^{(i)}$ at time i can be expressed as follows:

$$\begin{array}{l}{P}_c^{\left(i\right)}=\left[\mathrm{1}-\left(\mathrm{1}-q_{\mathrm{1}}^{\left(i\right)}\right)q_{\mathrm{2}}^{\left(i\right)}\right]P_{c\mathrm{1}}^{\left(i\right)}\\ \phantom{\text{ii}}+\left[\mathrm{1}-\left(\mathrm{1}-q_{\mathrm{2}}^{\left(i\right)}\right)q_{\mathrm{1}}^{\left(i\right)}\right]P_{c\mathrm{2}}^{\left(i\right)}.\end{array}$$

(7)

4. Request Scheduling Game

In this section, we introduce the request scheduling game. By modeling the game as a 3-player noncooperative game, we obtain the NEP at which the three players of ADR, NDR, and cluster heads all optimize their own utilities with no motivation to deviate the NEP.

4.1. The Three-Player Game

A multiplayer noncooperative game includes participants, policy for every player, and utility function for every player. The game is also a complete information static game in which every player knows the policy sets and the objective functions of others, but he does not know the policy choice of others. For the policy set, every player in this three-player game has infinite choices. We also suppose that every player in this game is selfish and rational. They choose the policy that can maximize their own utilities. The Nash Equilibrium Point is defined as the optimal policies chosen by all the players to optimize their own utility. At the NEP, no one has the motivation to deviate from this solution, because they will not gain more profit with other policies.

Consider a video sensor network with n heads at N different times. let the total arrival rate of abnormal requests be a constant β. Let ${\beta }_j^{(i)}$ express the arrival rate of abnormal requests to head j at time i. The policy set of ADR is $B^{(i)}=\{{\beta }_{\mathrm{1}}^{(i)},{\beta }_{\mathrm{2}}^{(i)},\dots ,{\beta }_n^{(i)}\}$ with the requirement as follows:

$$\begin{array}{cc}& {\displaystyle \sum }_{i=\mathrm{1}}^N‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^n‍{\beta }_j^{\left(i\right)}=\beta .\end{array}$$

(8)

Since abnormal data is time-sensitive, an abnormal request packet will be dropped if it exceeds the acceptable delay threshold. Therefore, we use the blocking rate to represent the quality demand from ADR. The utility function of ADR is to minimize the average blocking rate.

Let ${\lambda }_k^{(i)}$ express the arrival rate of normal requests to the head k at time i. The policy set of NDR is $A^{(i)}=\{{\lambda }_{\mathrm{1}}^{(i)},{\lambda }_{\mathrm{2}}^{(i)},\dots ,{\lambda }_n^{(i)}\}$ with the requirement as follows:

$$\begin{array}{cc}& {\displaystyle \sum }_{i=\mathrm{1}}^N‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^n‍{\lambda }_k^{\left(i\right)}=\lambda .\end{array}$$

(9)

NDR queue in the high priority queue in a head. We use the average delay to express the objective function.

Two heads can communicate through free load detection message. By using this message a busy head can find the free load head nearby and pass on the requests to them since the abnormal requests are immediate rejection type. Through this sharing way, heads cooperate to balance the load. We define $q_{jk}^{(i)}$ as the probability that head j passes on its own abnormal requests to head k. The policies for all the heads at time i can be formatted with the matrix as follows:

$$\begin{array}{cc}& C^{\left(i\right)}=\left[\begin{array}{cccc}{q}_{\mathrm{11}}^{\left(i\right)}& q_{\mathrm{12}}^{\left(i\right)}& \cdots & q_{\mathrm{1}n}^{\left(i\right)}\\ q_{\mathrm{21}}^{\left(i\right)}& q_{\mathrm{22}}^{\left(i\right)}& \cdots & q_{\mathrm{2}n}^{\left(i\right)}\\ & ⋮& & \\ q_{n\mathrm{1}}^{\left(i\right)}& q_{n\mathrm{2}}^{\left(i\right)}& \cdots & q_{nn}^{\left(i\right)}\end{array}\right]\end{array}$$

(10)

with the constraints of ${\sum }_{k=\mathrm{1}}^n‍q_{jk}^{(i)}=\mathrm{1}$ , $\mathrm{1}\le j\le n$ , $\mathrm{1}\le i\le N$ .

According to the definition of the NEP, given the utility function f, the policy set $(A^{*},B^{*},C^{*})=(A^{(\mathrm{1})*},\dots ,A^{(N)*},B^{(\mathrm{1})*},\dots ,B^{(N)*},C^{(\mathrm{1})*},\dots ,C^{(N)*})$ is a NEP, if $f(A^{*},B^{*},C^{*})\ge f(A,B,C)$ .

4.2. The Game Theoretic Formulae

According to (8), we can get the probability that head k at time i shares at least one request. This probability is shown as follows:

$$\begin{array}{cc}& Q_k^{\left(i\right)}=\mathrm{1}-{\displaystyle \prod }_{j=\mathrm{1}}^n‍\left(\mathrm{1}-q_{jk}^{\left(i\right)}\right),\end{array}$$

(11)

where $\mathrm{1}\le k\le n$ .

Based on the definitions and constraints above, we obtain the utility objective for the three players in this game.

The ADR wants to minimize the blocking rate which is expressed as follows:

$$\begin{array}{cc}& P_C^{\left(i\right)}={\displaystyle \sum }_{k=\mathrm{1}}^n{Q}_k^{\left(i\right)}·\frac{{\lambda }_k^{\left(i\right)}+{{\displaystyle \sum }}_{j=\mathrm{1}}^n‍{\beta }_j^{\left(i\right)}{q}_{jk}^{\left(i\right)}}{{\mu }_k^{\left(i\right)}+{{\displaystyle \sum }}_{j=\mathrm{1}}^n‍{\beta }_j^{\left(i\right)}{q}_{jk}^{\left(i\right)}}.\end{array}$$

(12)

Then we get the average blocking rate in the whole networking by weighting $P_c^{(i)}$ with fraction of abnormal request arrival rate as follows:

$$\begin{array}{cc}& \overline{P_C}={\displaystyle \sum }_{i=\mathrm{1}}^N‍\frac{{{\displaystyle \sum }}_{j=\mathrm{1}}^n‍{\beta }_j^{\left(i\right)}}{\beta }·P_C^{\left(i\right)}.\end{array}$$

(13)

The NDR wants to minimize the response delay of the normal requests. The delay of head k and the average delay of the whole networking are expressed as follows:

$$\begin{array}{cc}& D_k^{\left(i\right)}=\frac{{\lambda }_k^{\left(i\right)}+{{\displaystyle \sum }}_{j=\mathrm{1}}^n‍{\beta }_j^{\left(i\right)}{q}_{jk}^{\left(i\right)}}{\left({\mu }_k^{\left(i\right)}+{{\displaystyle \sum }}_{j=\mathrm{1}}^n‍{\beta }_j^{\left(i\right)}{q}_{jk}^{\left(i\right)}\right)\left({\mu }_k^{\left(i\right)}-{\lambda }_k^{\left(i\right)}\right)},\end{array}$$

(14)

$$\begin{array}{cc}& \overline{D}={\displaystyle \sum }_{i=\mathrm{1}}^N‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^n‍\frac{{\lambda }_k^{\left(i\right)}}{\lambda }·D_k^{\left(i\right)}.\end{array}$$

(15)

With the queue intensity $L_k^{(i)}=({\lambda }_k^{(i)}+{\sum }_{j=\mathrm{1}}^n‍{\beta }_j^{(i)}{q}_{jk}^{(i)})/{\mu }_k^{(i)}$ in head k, we get the load balancing index as follows:

$$\begin{array}{cc}& \overline{E}={\displaystyle \sum }_{i=\mathrm{1}}^N‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^n‍{\left(L_k^{\left(i\right)}\right)}^{\mathrm{2}}.\end{array}$$

(16)

Each player in the game chooses policy to optimize its own utility objective function.

ADR solves the following problem.

Minimize

$$\begin{array}{l}{L}_{\overline{P_c}}\left(A^{*},B,C^{*}\right)\\ \phantom{\text{wi}}={\displaystyle \sum }_{i=\mathrm{1}}^N‍\frac{{{\displaystyle \sum }}_{j=\mathrm{1}}^n‍{\beta }_j^{\left(i\right)}}{\beta }·P_C^{\left(i\right)}\\ \phantom{\text{wwii}}-u_p\left({\displaystyle \sum }_{i=\mathrm{1}}^N‍{\displaystyle \sum }_{j=\mathrm{1}}^n‍{\beta }_j^{\left(i\right)}-\beta \right)-{\displaystyle \sum }_{i=\mathrm{1}}^N‍\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^n‍v_{p_{ij}}{\beta }_j^{\left(i\right)}.\end{array}$$

(17)

With respect to constraints,

$$\begin{array}{l}{\displaystyle \sum }_{i=\mathrm{1}}^N‍\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^n{\beta }_j^{\left(i\right)}-\beta =\mathrm{0},\hspace{1em}\frac{v_{p_{ij}}}{{\beta }_j^{\left(i\right)}}=0,\\ \phantom{\text{wwwwii}}\mathrm{1}\le i\le N,\hspace{1em}\mathrm{1}\le j\le n.\end{array}$$

(18)

NDR solves the following problem.

Minimize

$$\begin{array}{l}{L}_{\overline{D}}\left(A,B^{*},C^{*}\right)\\ \hspace{1em}={\displaystyle \sum }_{i=\mathrm{1}}^N‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^n‍\frac{{\lambda }_k^{\left(i\right)}}{\lambda }·D_K^{\left(i\right)}\\ \hspace{1em}\hspace{1em}-u_D\left({\displaystyle \sum }_{i=\mathrm{1}}^N‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^n‍{\lambda }_k^{\left(i\right)}-\lambda \right)-{\displaystyle \sum }_{i=\mathrm{1}}^N‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^n‍v_{D_{ik}}{\lambda }_k^{\left(i\right)}.\end{array}$$

(19)

With respect to constraints,

$$\begin{array}{l}{\displaystyle \sum }_{i=\mathrm{1}}^N‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^n‍{\lambda }_k^{\left(i\right)}-\lambda =\mathrm{0},\hspace{1em}\hspace{1em}{v}_{D_{ik}}{\lambda }_k^{\left(i\right)}=\mathrm{0},\\ \phantom{\text{wwwwwwwii}}\mathrm{1}\le i\le N,\hspace{1em}\mathrm{1}\le k\le n.\end{array}$$

(20)

Cluster heads solve the following problem.

Minimize

$$\begin{array}{l}{L}_{\overline{E}}\left(A^{*},B^{*},C\right)\\ \hspace{1em}={\displaystyle \sum }_{i=\mathrm{1}}^N‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^n‍{\left(L_k^{\left(i\right)}\right)}^{\mathrm{2}}-{\displaystyle \sum }_{i=\mathrm{1}}^N‍{\displaystyle \sum }_{k=\mathrm{1}}^n‍u_{E_j}^{\left(i\right)}\left({\displaystyle \sum }_{k=\mathrm{1}}^n‍q_{jk}^{\left(i\right)}-\mathrm{1}\right)\\ \hspace{1em}\hspace{1em}-{\displaystyle \sum }_{i=\mathrm{1}}^N‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^n‍\hspace{0.17em}{\displaystyle \sum }_{j=\mathrm{1}}^n‍v_{E_{jk}}{q}_{jk}^{\left(i\right)}.\end{array}$$

(21)

With respect to constraints,

$$\begin{array}{l}{\displaystyle \sum }_{k=\mathrm{1}}^n‍q_{jk}^{\left(i\right)}-\mathrm{1}=\mathrm{0},\hspace{1em}\hspace{1em}{v}_{E_{jk}}{q}_{jk}^{\left(i\right)}=\mathrm{0},\\ \phantom{\text{wwww}}\mathrm{1}\le i\le N,\hspace{1em}\mathrm{1}\le k,\hspace{0.17em}\hspace{0.17em}j\le n.\end{array}$$

(22)

To sum up, we can obtain the NEP solution from the following equation group:

$$\begin{array}{cc}& \frac{P_C^{\left(i\right)}}{\beta }+\frac{{{\displaystyle \sum }}_{j=\mathrm{1}}^n‍{\beta }_j^{{\left(i\right)}^{*}}}{\beta }·\frac{\partial P_C^{\left(i\right)}}{\partial {\beta }_j^{(i{)}^{*}}}-u_p-v_{p_{ij}}=\mathrm{0},\\ {\displaystyle \sum }_{i=\mathrm{1}}^N‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^n‍{\beta }_k^{{\left(i\right)}^{*}}-\beta =\mathrm{0},\\ v_{p_{ij}}{\beta }_j^{{\left(i\right)}^{*}}=\mathrm{0},\\ \frac{D_k^{\left(i\right)}}{\lambda }+\frac{{\lambda }_k^{{\left(i\right)}^{*}}}{\lambda }·\frac{\partial D_k^{\left(i\right)}}{\partial {\lambda }_k^{{\left(i\right)}^{*}}}-u_D-v_{D_{ik}}=\mathrm{0},\\ {\displaystyle \sum }_{i=\mathrm{1}}^N‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^n‍{\lambda }_k^{{\left(i\right)}^{*}}-\lambda =\mathrm{0},\\ v_{D_{ik}}{\lambda }_k^{{\left(i\right)}^{*}}=\mathrm{0},\\ \mathrm{2}{L}_k^{\left(i\right)}·\frac{\partial L_k^{\left(i\right)}}{\partial q_{jk}^{{\left(i\right)}^{*}}}-u_{E_j}^{\left(i\right)}-v_{E_{jk}}=\mathrm{0},\\ {\displaystyle \sum }_{k=\mathrm{1}}^n‍q_{jk}^{{\left(i\right)}^{*}}-\mathrm{1}=\mathrm{0},\\ v_{E_{jk}}{q}_{jk}^{{\left(i\right)}^{*}}=\mathrm{0}.\end{array}$$

(23)

NEP solution is the optimal policy for each player to maximize their own utility. As rational player, no one has the motivation to deviate from this optimal policy choice.

5. Property Validation

In this section, we give some theorems and propositions with their proofs to reveal some properties of the NEP solution. We prove the existence and stability of NEP as well as the advantage of NEP and handover efficiency.

Theorem 1.

A Nash Equilibrium Point exists in the request scheduling game.

Proof.

As defined in Section 3, we use A, B, and C, respectively, to represent the policy sets of NDR, ADR, and heads. So the whole policy space of all the three players will be $S=A\times B\times C$ . Then we use $(a,b,c)$ to represent a point in the space S. We can see that A, B, and C are all the subset of Hausdorff spaces. With the total arrival rate constraints (8) and (9) and the total sharing probability constraint (10) in Section 3, we can reason that the sets A, B, and C are all closed. We can also prove that A, B, and C are all convex sets (proof will be given in Appendix A).

Average delay $\overline{D}(S)$ , average blocking rate $\overline{P_c}(S)$ , and load balancing index $\overline{E}(S)$ are the utility functions in this game. According to (13), (15), and (16), mapping $\overline{D}:S\to R$ , mapping $\overline{P_c}:S\to R$ , and mapping $\overline{E}:S\to R$ are all continuous. For policy a in set A, delay $a\to \overline{D}(a,b,c)$ is pseudoconvex function on A. In the same way, blocking rate $b\to \overline{P_c}(a,b,c)$ and load balancing index $c\to \overline{E}(a,b,c)$ are both pseudoconvex functions on B and C (proof will be given in Appendix B).

For NDR and its policy set A, we define the set value mapping $F_A:B\times C\to P_{\mathrm{0}}(A)$ with $\forall (b,c)\in B\times C$ as follows:

$$\begin{array}{cc}& F_A\left(b,c\right)=\left\{a^{*}\in A:\overline{D}\left(a^{*},b,c\right)=\underset{a\in A}{\min }\overline{D}\left(a,b,c\right)\right\}.\end{array}$$

(24)

For ADR and its policy set B, we define the set value mapping $F_B:A\times C\to P_{\mathrm{0}}(B)$ with $\forall (a,c)\in A\times C$ as follows:

$$\begin{array}{cc}& F_B\left(a,c\right)=\left\{b^{*}\in B:\overline{P_c}\left(a,b^{*},c\right)=\underset{b\in B}{\min }\overline{P_c}\left(a,b,c\right)\right\}.\end{array}$$

(25)

For heads and the policy set C, we define the set value mapping $F_C:A\times B\to P_{\mathrm{0}}(C)$ with $\forall (a,b)\in A\times B$ as follows:

$$\begin{array}{cc}& F_c\left(a,b\right)=\left\{c^{*}\in C:\overline{E}\left(a,b,c^{*}\right)=\underset{c\in C}{\min }\overline{E}\left(a,b,c\right)\right\}.\end{array}$$

(26)

Given $r={\inf }_{(b,c)\in B\times C}({\min }_{a\in A}\overline{D}(a,b,c))$ , we can see that, for any $(b,c)\in B\times C$ , $\overline{D}(a^{*},b,c)\ge r$ . Then we deduce that $F_A(b,c)$ is the convex closed set on A and $F_A:B\times C\to P_{\mathrm{0}}(A)$ is upper-continuous. For $F_B$ and $F_C$ , we have the same conclusions. So we define the set value mapping $F:S\to P_{\mathrm{0}}(S)$ , for any $(a,b,c)\in S$ , as follows:

$$\begin{array}{cc}& F\left(a,b,c\right)=F_A\left(b,c\right)\times F_B\left(a,c\right)\times F_C\left(a,b\right).\end{array}$$

(27)

Mapping F is upper-continuous with its convex closed value set $F(a,b,c)$ . Based on Fan-Glicksberg fixed point theorem [18], for existence of $(a^{*},b^{*},c^{*})\in S$ , we have $(a^{*},b^{*},c^{*})\in F(a^{*},b^{*},c^{*})$ . To conclude, a NEP exists in this game.

Theorem 2.

The NEP solution to the request scheduling game is stable.

Proof.

Policy sets A, B, and C are all closed and convex subsets in Hausdorff spaces. Objective mappings $a\to \overline{D}(a,b,c)$ , $b\to \overline{P_c}(a,b,c)$ , and $c\to \overline{E}(a,b,c)$ are all continuous and pseudoconvex functions. Let functional space be $F=(\overline{D},\overline{P_c},\overline{E})$ . Set value mapping is a usco mapping on game space F. Because policy spaces A, B, and C are all normed linear spaces (proof will be given in Appendix C), there is a dense complement set, in which any f belonging to F is general. In general game f, for any $(a,b,c)\in N(f)$ , (a,b,c) is a general equilibrium point [19].

This theorem has practical significance in video sensor networks. In this game, when game function, such as average delay, changes slightly into another similar but different formulation, the new NEP will not vary greatly. A NEP represents the results of data-reporting request assignment and networking resource allocation. We know that accidents in the networking always happen without in-time response. As shown in (23), changes of processor in the head will lead to changes of the service rate μ. Then the whole game function of delay will change a little. Because of the stability of the NEP solution, even still following the proper policies, quality of service and performance of networking will not be affected too much. Hence, the NEP can give a smooth transition in some emergent accidents. It is meaningful to stable surveillance.

We will prove that the NEP solution and handover mechanism outperform other mechanisms in some difficult working conditions.

Proposition 3.

Given the arrival rates for both ADR and NDR as ${\lambda }_{\mathrm{1}}$ and ${\beta }_{\mathrm{1}}$ as well as the service rate ${\mu }_{\mathrm{1}}$ , the normal request response delay $D_{\mathrm{1}}^{(i)}$ is less than the delay $W_{\mathrm{1}}$ in M/M/1 model, if the rates satisfy ${\lambda }_{\mathrm{1}}/{\beta }_{\mathrm{1}}\to \infty$ .

Proof.

We use the waiting time of a normal request packet to express the delay in M/M/1. Delay in M/M/1 and delay of the handover mechanism can be expressed as follows:

$$\begin{array}{cc}& W_{\mathrm{1}}=\frac{{\lambda }_{\mathrm{1}}+{\beta }_{\mathrm{1}}}{{\mu }_{\mathrm{1}}\left({\mu }_{\mathrm{1}}-{\lambda }_{\mathrm{1}}-{\beta }_{\mathrm{1}}\right)},\\ D_{\mathrm{1}}^{\left(i\right)}=\frac{{\lambda }_{\mathrm{1}}+q_{\mathrm{1}}{\beta }_{\mathrm{1}}+\left(\mathrm{1}-q_{\mathrm{2}}\right){\beta }_{\mathrm{2}}}{\left({\mu }_{\mathrm{1}}+q_{\mathrm{1}}{\beta }_{\mathrm{1}}+\left(\mathrm{1}-q_{\mathrm{2}}\right){\beta }_{\mathrm{2}}\right)\left({\mu }_{\mathrm{1}}-{\lambda }_{\mathrm{1}}\right)}.\end{array}$$

(28)

By using the condition ${\lambda }_{\mathrm{1}}/{\beta }_{\mathrm{1}}\to \infty$ , $\mathrm{1}/{\lambda }^{\mathrm{2}}\to \mathrm{0}$ , we can get the ratio of two delays. Then we use the high order infinitesimal of $\mathrm{1}/{\lambda }_{\mathrm{2}}$ to obtain the limit of the ratio.

Consider

$$\begin{array}{l}\frac{D_{\mathrm{1}}^{\left(i\right)}}{W}=\frac{{\mu }_{\mathrm{1}}+O\left(\mathrm{1}/{\lambda }_{\mathrm{1}}^{\mathrm{2}}\right)}{{\mu }_{\mathrm{1}}+q_{\mathrm{1}}{\beta }_{\mathrm{1}}+(\mathrm{1}-q_{\mathrm{2}}){\beta }_{\mathrm{2}}+O\left(\mathrm{1}/{\lambda }_{\mathrm{1}}^{\mathrm{2}}\right)}\\ \begin{array}{l}⟶\frac{{\mu }_{\mathrm{1}}}{{\mu }_{\mathrm{1}}+q_{\mathrm{1}}{\beta }_{\mathrm{1}}+\left(\mathrm{1}-q_{\mathrm{2}}\right){\beta }_{\mathrm{2}}}<\mathrm{1}.\end{array}\end{array}$$

(29)

So, we get $D_{\mathrm{1}}^{(i)}<W$ .

The limitation condition ${\lambda }_{\mathrm{1}}/{\beta }_{\mathrm{1}}\to \infty$ can be regarded as the situation that the number of normal requests is too much greater than abnormal requests. In this situation, normal data are the main load of networking comparing with abnormal data. It is necessary to pay attention to the quality demand of NDR. Proposition 3 indicates that by using handover the request delay is less than the delay in nondifferential M/M/1 model.

Proposition 4.

On condition ${\beta }_{\mathrm{1}}/{\lambda }_{\mathrm{1}}\to \infty$ , ${\beta }_{\mathrm{2}}/{\lambda }_{\mathrm{2}}\to \infty$ , handover mechanism performs like model M/M/1(1).

Proof.

Low priority queue for abnormal requests is immediate rejection. Suppose that there are two heads and the probabilities of sharing are $q_{\mathrm{1}}$ and $q_{\mathrm{2}}$ . According to (11), we get the weights $Q_{\mathrm{1}}$ and $Q_{\mathrm{2}}$ , which mean that no abnormal request is handed over to head 1 or 2,

$$\begin{array}{cc}& Q_{\mathrm{1}}=\mathrm{1}-\left(\mathrm{1}-q_{\mathrm{1}}\right)q_{\mathrm{2}},\hspace{1em}\hspace{1em}{Q}_{\mathrm{2}}=\mathrm{1}-\left(\mathrm{1}-q_{\mathrm{2}}\right)q_{\mathrm{1}}.\end{array}$$

(30)

For M/M/1 $(1)$ model, weighted blocking rate for abnormal requests to the two heads are as follows:

$$\begin{array}{cc}& \overline{\phi }=Q_{\mathrm{1}}·\frac{{\lambda }_{\mathrm{1}}+{\beta }_{\mathrm{1}}}{{\mu }_{\mathrm{1}}+{\lambda }_{\mathrm{1}}+{\beta }_{\mathrm{1}}}+Q_{\mathrm{2}}·\frac{{\lambda }_{\mathrm{2}}+{\beta }_{\mathrm{2}}}{{\mu }_{\mathrm{2}}+{\lambda }_{\mathrm{2}}+{\beta }_{\mathrm{2}}}.\end{array}$$

(31)

In the handover mechanism, weighted blocking rate for abnormal requests to the two heads are expressed as follows:

$$\begin{array}{l}{P}_c^{\left(i\right)}=Q_{\mathrm{1}}·\frac{{\lambda }_{\mathrm{1}}+q_{\mathrm{1}}{\beta }_{\mathrm{1}}+\left(\mathrm{1}-q_{\mathrm{2}}\right){\beta }_{\mathrm{2}}}{{\mu }_{\mathrm{1}}+q_{\mathrm{1}}{\beta }_{\mathrm{1}}+\left(\mathrm{1}-q_{\mathrm{2}}\right){\beta }_{\mathrm{2}}}\\ \hspace{1em}+Q_{\mathrm{2}}·\frac{{\lambda }_{\mathrm{2}}+q_{\mathrm{2}}{\beta }_{\mathrm{2}}+\left(\mathrm{1}-q_{\mathrm{1}}\right){\beta }_{\mathrm{1}}}{{\mu }_{\mathrm{2}}+q_{\mathrm{2}}{\beta }_{\mathrm{2}}+\left(\mathrm{1}-q_{\mathrm{1}}\right){\beta }_{\mathrm{1}}}\end{array}$$

(32)

when ${\beta }_{\mathrm{1}}/{\lambda }_{\mathrm{1}}\to \infty$ , ${\beta }_{\mathrm{2}}/{\lambda }_{\mathrm{2}}\to \infty$ , $\mathrm{1}/{\beta }_{\mathrm{1}}\to \infty$ , $\mathrm{1}/{\beta }_{\mathrm{2}}\to \infty$ , we get

$$\begin{array}{cc}& \frac{P_c^{\left(i\right)}}{\overline{\phi }}=\frac{Q_{\mathrm{1}}+Q_{\mathrm{2}}+O(\mathrm{1}/{\beta }_{\mathrm{1}})+O(\mathrm{1}/{\beta }_{\mathrm{2}})}{Q_{\mathrm{1}}+Q_{\mathrm{2}}+O(\mathrm{1}/{\beta }_{\mathrm{1}})+O(\mathrm{1}/{\beta }_{\mathrm{2}})}⟶\mathrm{1}.\end{array}$$

(33)

The M/M/1 $(1)$ model is used to serve the requests, just because the queue model has to accommodate the condition ${\beta }_{\mathrm{1}}/{\lambda }_{\mathrm{1}}\to \infty$ , ${\beta }_{\mathrm{2}}/{\lambda }_{\mathrm{2}}\to \infty$ , which means that abnormal requests are much more than normal requests. Additionally, abnormal request has a delay threshold and will not wait for a long period of time. Since too little normal requests need to be processed, the main objective is to serve the ADR. M/M/1 $(1)$ is one of proper models for abnormal requests. Proposition 4 indicates that handover mechanism performs as well as M/M/1 $(1)$ model when abnormal data imposes tremendous load on the networking.

Proposition 5.

When ${\mu }_{\mathrm{1}}/{\mu }_{\mathrm{2}}<\mathrm{1}$ , ${\beta }_{\mathrm{1}}/{\beta }_{\mathrm{2}}\to \infty$ , LSG model has a smaller load balancing index than M/M/1 model.

Proof.

Suppose that there are two heads to do handover. We use $M^{\mathrm{2}}$ to express the balancing index in M/M/1, and $E^{\mathrm{2}}$ to express the index between heads with handover

$$\begin{array}{l}{M}^{\mathrm{2}}={\left(\frac{{\lambda }_{\mathrm{1}}+{\beta }_{\mathrm{1}}}{{\mu }_{\mathrm{1}}}\right)}^{\mathrm{2}}+{\left(\frac{{\lambda }_{\mathrm{2}}+{\beta }_{\mathrm{2}}}{{\mu }_{\mathrm{2}}}\right)}^{\mathrm{2}},\\ \hspace{0.17em}\hspace{0.17em}{E}^{\mathrm{2}}={\left(\frac{{\lambda }_{\mathrm{1}}+q_{\mathrm{1}}{\beta }_{\mathrm{1}}+\left(\mathrm{1}-q_{\mathrm{2}}\right){\beta }_{\mathrm{2}}}{{\mu }_{\mathrm{1}}}\right)}^{\mathrm{2}}\\ \hspace{0.17em}\hspace{0.17em}\hspace{0.17em}\hspace{1em}\hspace{1em}+{\left(\frac{{\lambda }_{\mathrm{2}}+q_{\mathrm{2}}{\beta }_{\mathrm{2}}+\left(\mathrm{1}-q_{\mathrm{1}}\right){\beta }_{\mathrm{1}}}{{\mu }_{\mathrm{2}}}\right)}^{\mathrm{2}}.\end{array}$$

(34)

On the conditions ${\mu }_{\mathrm{1}}/{\mu }_{\mathrm{2}}<\mathrm{1}$ , ${\beta }_{\mathrm{1}}/{\beta }_{\mathrm{2}}\to \infty$ , $\mathrm{1}/{\beta }_{\mathrm{1}}^{\mathrm{2}}\to \mathrm{0}$ , the ratio can be limited with high order infinitesimal of $\mathrm{1}/{\beta }_{\mathrm{1}}^{\mathrm{2}}$ as follows:

$$\begin{array}{cc}& \frac{M^{\mathrm{2}}}{E^{\mathrm{2}}}=\frac{\left(\mathrm{1}/{\mu }_{\mathrm{1}}^{\mathrm{2}}\right)+O\left(\mathrm{1}/{\beta }_{\mathrm{1}}^{\mathrm{2}}\right)}{\left(q_{\mathrm{2}}^{\mathrm{2}}/{\mu }_{\mathrm{1}}^{\mathrm{2}}\right)+\left({\left(\mathrm{1}-q_{\mathrm{2}}\right)}^{\mathrm{2}}/{\mu }_{\mathrm{2}}^{\mathrm{2}}\right)+O\left(\mathrm{1}/{\beta }_{\mathrm{1}}^{\mathrm{2}}\right)}.\end{array}$$

(35)

By using the condition and square inequality, we get

$$\begin{array}{cc}& \frac{M^{\mathrm{2}}}{E^{\mathrm{2}}}⟶\frac{{\mu }_{\mathrm{2}}^{\mathrm{2}}}{q_{\mathrm{1}}^{\mathrm{2}}{\mu }_{\mathrm{2}}^{\mathrm{2}}+{\left(\mathrm{1}-q_{\mathrm{1}}\right)}^{\mathrm{2}}{\mu }_{\mathrm{1}}^{\mathrm{2}}}>\frac{\mathrm{1}}{q_{\mathrm{1}}^{\mathrm{2}}+{\left(\mathrm{1}-q_{\mathrm{1}}\right)}^{\mathrm{2}}}\ge \mathrm{1}.\end{array}$$

(36)

The nodes of high process ability are supposed to serve more packets in accordance with their practical capacity. To analyze the condition ${\mu }_{\mathrm{1}}/{\mu }_{\mathrm{2}}<\mathrm{1}$ , ${\beta }_{\mathrm{1}}/{\beta }_{\mathrm{2}}\to \infty$ , we find that this is the situation in which the two heads may lose balance. Because the processor in head 2 is stronger than the one in head 1, head 2 is supposed to process more requests than head 1, yet, there are much more requests arriving at head 1 than head 2. This situation will test the adjustability of networking. Proposition 5 indicates that the handover model shows better adjustability than M/M/1.

Proposition 6.

The NEP solution shows inefficiency as the number of heads increases on conditions as follows:

$$\begin{array}{cc}& {\lambda }_{\mathrm{1}}={\lambda }_{\mathrm{2}}=\cdots ={\lambda }_M,\\ {\beta }_{\mathrm{1}}={\beta }_{\mathrm{2}}=\cdots ={\beta }_M,\\ {\mu }_{\mathrm{1}}={\mu }_{\mathrm{2}}=\cdots ={\mu }_M.\end{array}$$

(37)

Proof.

By solving the equation group (23) to get the NEP, we have a load balancing constraint. According to the format of the balancing index and the square inequality, we have

$$\begin{array}{cc}& {\displaystyle \sum }_{i=\mathrm{1}}^M‍{\left(L_i\right)}^{\mathrm{2}}\ge \frac{{\left({{\displaystyle \sum }}_{i=\mathrm{1}}^M‍L_i\right)}^{\mathrm{2}}}{\mathrm{2}}\end{array}$$

(38)

with the equalization condition $L_{\mathrm{1}}=L_{\mathrm{2}}=\cdots =L_M$ . Then we can figure out the sharing probability for each head in different cases.

When $M=n$ , we get $q_{jk}=\mathrm{1}/n$ , $\mathrm{1}\le j,k\le n$ .

When $M=n-\mathrm{1}$ , we get $q_{rm}^{\prime }=\mathrm{1}/(n-\mathrm{1})$ , $\mathrm{1}\le r,m\le n-\mathrm{1}$ .

We define the inefficiency indexes F and $F^{\prime }$ as follows:

$$\begin{array}{cc}& F=n·{\left(\mathrm{1}-\frac{\mathrm{1}}{n}\right)}^n·\left(\mathrm{1}-\lambda \mathrm{\Delta }t\right),\\ F^{\prime }=\left(n-\mathrm{1}\right)·{\left(\mathrm{1}-\frac{\mathrm{1}}{n-\mathrm{1}}\right)}^{n-\mathrm{1}}·\left(\mathrm{1}-\lambda \mathrm{\Delta }t\right),\end{array}$$

(39)

where $(\mathrm{1}-\lambda \mathrm{\Delta }t)$ is the probability of free load over infinitesimal period and $(\mathrm{1}-\mathrm{1}/n{)}^n$ is the probability that no abnormal requests are shared. Because $((n-\mathrm{1})/n)·(\mathrm{1}-\mathrm{1}/n{)}^{n-\mathrm{1}}>((n-\mathrm{1})/n)·(\mathrm{1}-\mathrm{1}/(n-\mathrm{1}){)}^{n-\mathrm{1}}$ , we get

$$\begin{array}{cc}& F>F^{\prime }.\end{array}$$

(40)

The inefficiency index can be regarded as the degree of wasting networking resource. It is the total probability that one node has to do some work but it does not. On the conditions in Proposition 6, every head in a LSG has the same work load and process ability. But in an infinitesimal period every head has a probability of free load by NDR but receive no abnormal request. It is a waste of networking resource. We figure out the total probability of inefficiency and find that the index gets larger as the head number increases. This proposition also has a practical significance. Because of the similar process ability and same work load, each head does not have motivation to share the abnormal requests. No share means inefficiency of handover. Therefore, we prefer some distinction in head selection.

6. Numerical Results

We use Matlab to evaluate the performance of our proposed handover mechanism and game theoretic scheduling method. We consider the single-hop case. It has 6 heads that response to all the data-reporting requests from 30 sensor nodes. We set the 1st, 3rd, and 5th nodes to have capacity of 4.2 Mbps, and the 2nd, 4th, and 6th nodes to have capacity of 3.3 Mbps. This is because homogeneous nodes may cause the inefficiency which has been shown in Proposition 6. The ADR and NDR packet sizes are both 1 MB. Accordingly, the average service rates of the 1st and 2nd nodes are ${\mu }_{\mathrm{1}}=\mathrm{25}$  packets/min and ${\mu }_{\mathrm{2}}=\mathrm{20}$  packets/min. The 30 sensor nodes generate request packets in a Poisson distribution, and the average packet arrival rate $\lambda +\beta$ is set to be less than the total service rate μ, thus keeping the networking stability. According to the capacities, the total service rate 135 requests/min is the upper bound of load. The networking utilization can be expressed as $\rho ={\sum }_{i=\mathrm{1}}^{\mathrm{6}}‍({\lambda }_i+{\beta }_i)/{\sum }_{i=\mathrm{1}}^{\mathrm{6}}‍{\mu }_i$ . We will evaluate the networking performance in different utilization values ranging over $(\mathrm{0,1})$ .

6.1. Handover Mechanism

By employing the game theoretic optimization to get the NEP solution, we record the probability changes with the ratio of normal request rate at head 1 to the rate at head 2. Probabilities $q_{\mathrm{12}}^{(\mathrm{1})}$ and $q_{\mathrm{21}}^{(\mathrm{1})}$ in vertical axis corresponding to ten values of ${\lambda }_{\mathrm{1}}^{(\mathrm{1})}/{\lambda }_{\mathrm{2}}^{(\mathrm{1})}$ in horizontal axis are shown in Figure 3(a). On the first half of horizontal axis, we have ${\lambda }_{\mathrm{1}}^{(\mathrm{1})}/{\lambda }_{\mathrm{2}}^{(\mathrm{1})}<\mathrm{1}$ . Normal request arriving rate at head 1 is less than head 2, yet, head 1 has a capacity larger than head 2. It means that unbalance load will happen. To keep load balance, head 1 lowers the probability of passing abnormal request on to head 2. Meanwhile, head 2 raises the probability to pass on the requests. As shown in Figure 3, when the ratio reaches a value a little larger than 1, load balance is achieved. At the horizontal values larger than but close to 1, the system does not have an obvious tendency to lose balance. So, the two heads both experience a section of probability fluctuation across the horizontal axis. The section of fluctuation on the second half of horizon axis can be interpreted as the self-adjustment of heads to obtain the load balance again. When the ratio of is large enough, as shown in right section in Figure 3(a), heads have the definite orientation to change their probability of handing request over. Figure 3(b) shows more details of the adjustment and fluctuation by taking 100 ratio values into account. We can see the similar change tendency as Figure 3(a) on the first half of coordinate. We use the normal request ratio rather than abnormal request ratio, because large amount of normal requests is the main reason to make no free load head for the ADR; heads need to share abnormal requests frequently.

Figure 3

Probability of two heads passing on abnormal requests to each other: (a) 10 values of ratio ${\lambda }_{\mathrm{1}}/{\lambda }_{\mathrm{2}}$ ; (b) 100 values of ratio ${\lambda }_{\mathrm{1}}/{\lambda }_{\mathrm{2}}$ .

From Figure 3, we see the interaction between request arriving amount and heads’ policy based on handover. In different state of arriving rate, heads always use the NEP solution to alleviate load and keep balance through handover.

6.2. Performance Evaluation

Let λ be the total normal request arriving rate. Let β be the total abnormal request arriving rate. We record the simulation results in two cases of $\lambda /\beta =\mathrm{2}$ and $\lambda /\beta =\mathrm{1}$ . So we get 9 values of $\lambda +\beta$ in 9 utilization values as a sequence as $[\mathrm{13.5,27,40.5,54,67.5,81,94.5,108,121.5}]$ (requests/min).

In our proposed game theoretic request scheduling based on handover, we use the NEP from (23) to make head selection to optimize utility functions of three players in the game as we discussed in Section 3.

On condition of M/M/1, the solution can be figured out with a load balance constraint as follows:

$$\begin{array}{cc}& \frac{{\lambda }_{\mathrm{1}}+{\beta }_{\mathrm{1}}}{{\mu }_{\mathrm{1}}}=\frac{{\lambda }_{\mathrm{2}}+{\beta }_{\mathrm{2}}}{{\mu }_{\mathrm{2}}}=\cdots =\frac{{\lambda }_{\mathrm{6}}+{\beta }_{\mathrm{6}}}{{\mu }_{\mathrm{6}}}.\end{array}$$

(41)

In minimum delay selection method, based on M/M/1, optimization is to solve the problem

$$\begin{array}{cc}& \mathrm{Min}\hspace{0.17em}\overline{W}={\displaystyle \sum }_{i=\mathrm{1}}^{\mathrm{6}}‍\frac{{\lambda }_i}{\lambda }·\frac{{\lambda }_i+{\beta }_i}{{\mu }_i\left({\mu }_i-{\lambda }_i-{\beta }_i\right)}.\end{array}$$

(42)

In minimum blocking probability method based on M/M/1 $(1)$ , optimization is to solve the problem

$$\begin{array}{cc}& \mathrm{Min}\hspace{0.17em}{\overline{\phi }}_c={\displaystyle \sum }_{i=\mathrm{1}}^{\mathrm{6}}‍\frac{{\beta }_i}{\beta }·\frac{{\lambda }_i+{\beta }_i}{\left({\mu }_i+{\lambda }_i+{\beta }_i\right)}.\end{array}$$

(43)

The NEP in our method contains three optimal solutions. Hence, we compare simulation results from three aspects. We compare our NEP with equal load and minimum delay solutions by delay simulation. For blocking rate, we show the comparison of our NEP with minimum blocking probability solution. In load index comparison, results of all the four optimizations will be illustrated.

6.2.1. Delay for NDR

Figure 4 shows three surfaces, which respectively represent the delay solutions of NEP, (minimum delay) MD [13], and (equal load) EL [14]. Each surface shows perform of an optimal delay method by giving delay value change with both ratio $\lambda /\beta$ and networking utilization. For normal requests, NEP outperforms MD and EL. Details are shown in Figure 5. In Figure 5(a), when ratio $\lambda /\beta =\mathrm{2}$ , we can see that NEP has lower delays than both of the other two methods when the networking utilization $\rho <\mathrm{0.6}$ . The NEP performs better than minimum delay method in all utilization points except $\rho =\mathrm{0.9}$ . The equal load method performs best only when $\rho =\mathrm{0.7}$ , yet, we can see that all the three methods perform similarly in $\rho =\mathrm{0.7}$ . In all the utilizations, average delays of both NEP and minimum delay are all lower than 0.15 min. When the ratio changes into $\lambda /\beta =\mathrm{1}$ , Figure 5(b) shows the comparison. The NEP has lower delays than both the other two methods when $\rho <\mathrm{0.7}$ except $\rho =\mathrm{0.3}$ . In particular in the point $\rho =\mathrm{0.9}$ , the NEP has significant dominance over the other two methods.

Figure 4

Comparison of average delays in different ratio $\lambda /\beta$ and networking utilization.

Figure 5

Comparison of average delays in (a) $\lambda /\beta =\mathrm{2}$ and (b) $\lambda /\beta =\mathrm{1}$ .

As shown in Figures 4 and 5, the dominance of NEP is not only in the situation that the networking has relatively small utilizations, but also in the scenario that large amount of load put on the networking. We consider the reason from two aspects. Although NEP solution has the similar optimizing algorithm and constraints as the minimum delay method, the NEP is based on the handover mechanism to balance load. Another reason is that each head use high and low priority queues to process two kinds of packets. The head drops or hand over abnormal request packets when necessary to ensure these request are processed in time.

6.2.2. Blocking Rate for ADR

Minimum blocking probability method based on M/M/1/ $(1)$ minimizes the average blocking rate. Figure 6 shows the respective surfaces of NEP and (minimum blocking rate) MB [15] on M/M/1/ $(1)$ . Blocking rate values change with ratio $\lambda /\beta$ and networking utilizations. For abnormal requests, NEP outperforms MB on M/M/1/ $(1)$ . Results in Figure 7(a) are on condition $\lambda /\beta =\mathrm{2}$ . We see that the NEP blocking rate is relatively stable and performs better than minimum blocking probability method when the networking utilizations are less than 0.6. As load increases further, the NEP blocking rate reaches high values. In Figure 7(b), we have total arriving rate ratio $\lambda /\beta =\mathrm{1}$ . Although NEP still performs better at most utilization points in a range $\rho <\mathrm{0.5}$ , the NEP blocking rate figure shows considerable fluctuation.

Figure 6

Comparison of average blocking rates in different ratio $\lambda /\beta$ and networking utilization.

Figure 7

Comparison of average blocking rates in (a) $\lambda /\beta =\mathrm{2}$ and (b) $\lambda /\beta =\mathrm{1}$ .

We draw two conclusions from the two figures. First, there is an optimal utilization range for blocking rate by NEP like $\rho <\mathrm{0.6}$ in Figure 7(a). In this range, live content delivery works well with a relatively low blocking probability. Second, performance fluctuation is mainly caused by the gradual reduction of ratio $\lambda /\beta$ . Increasing the number of both ADR and NDR do not lead to a fluctuation. When abnormal requests takes a considerable proportion of the total arriving rate, performance of blocking rate becomes unstable. In high utilization, high blocking rate for abnormal requests is reasonable. Rejection in time can let ADR find a new head as quickly as possible rather than wait a long period of time in the queue.

6.2.3. Load of Heads

According to (16), minimizing the index is a control and optimization process. we have

$$\begin{array}{cc}& {\displaystyle \sum }_{i=\mathrm{1}}^{\mathrm{3}}‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^{\mathrm{2}}‍{\left(L_k^{\left(i\right)}\right)}^{\mathrm{2}}\ge \left(\frac{\mathrm{1}}{\mathrm{2}}\right)·{\left({\displaystyle \sum }_{i=\mathrm{1}}^{\mathrm{3}}‍\hspace{0.17em}{\displaystyle \sum }_{k=\mathrm{1}}^{\mathrm{2}}‍\left(L_k^{\left(i\right)}\right)\right)}^{\mathrm{2}}.\end{array}$$

(44)

When expression on the right side of the inequality is a constant, we get the condition to equalize (44) as $L_{\mathrm{1}}^{(\mathrm{1})}=L_{\mathrm{2}}^{(\mathrm{1})}=L_{\mathrm{1}}^{(\mathrm{2})}=L_{\mathrm{2}}^{(\mathrm{2})}=L_{\mathrm{1}}^{(\mathrm{3})}=L_{\mathrm{2}}^{(\mathrm{3})}$ .

The NEP load index is figured out with (16). For other methods, the index is expressed as ${\sum }_{i=\mathrm{1}}^{\mathrm{6}}‍(({\lambda }_i+{\beta }_i)/{\mu }_i{)}^{\mathrm{2}}$ .

To evaluate the load balance of the four optimization methods, we let all the 6 heads have the same capacity of 4.2 Mbps. In addition, the total arriving rate $\lambda +\beta$ at each networking utilization point is a constant. As shown in Figure 8, all the four methods perform nearly the same in different utilizations and ratio $\lambda /\beta$ . The results indicate that NEP satisfies QoS demands of both ADR and NDR without losing load balance.

Figure 8

Comparison of load index in different ratio $\lambda /\beta$ and networking utilization.

7. Conclusion

In this paper, we propose a comprehensive way to satisfy the QoS demands of both normal and abnormal data-reporting requests in order to improve the accident discovery but not to interfere with the regular surveillance task in video sensor networks. The request scheduling game optimizes the utilities of both ADR and NDR and balances the load on cluster heads. A handover mechanism ensures that the abnormal requests are processed in time. Based on game theoretic analysis, we prove some properties of the NEP and the handover mechanism. Existence and stability of NEP ensure efficient optimization and good adjustability to some accidents in networks. Numerical analysis shows that the game strategic scheduling outperforms other scheduling methods that consider single objective (minimum delay or minimum blocking rate).