# Dynamic Channel Slot Allocation Scheme and Performance Analysis of Cyclic Quorum Multichannel MAC Protocol

Authors: Xing Hu; Linhua Ma; Shaocheng Huang; Tianyu Huang; Shiping Liu
Journal: Mathematical Problems in Engineering
 (2017)

---

## Abstract

In high diversity node situation, multichannel MAC protocol can improve the frequency efficiency, owing to fewer collisions compared with single-channel MAC protocol. And the performance of cyclic quorum-based multichannel (CQM) MAC protocol is outstanding. Based on cyclic quorum system and channel slot allocation, it can avoid the bottleneck that others suffered from and can be easily realized with only one transceiver. To obtain the accurate performance of CQM MAC protocol, a Markov chain model, which combines the channel-hopping strategy of CQM protocol and IEEE 802.11 distributed coordination function (DCF), is proposed. The results of numerical analysis show that the optimal performance of CQM protocol can be obtained in saturation bound situation. And then we obtain the saturation bound of CQM system by bird swarm algorithm. In addition, to improve the performance of CQM protocol in unsaturation situation, a dynamic channel slot allocation of CQM (DCQM) protocol is proposed, based on wavelet neural network. Finally, the performance of CQM protocol and DCQM protocol is simulated by Qualnet platform. And the simulation results show that the analytic and simulation results match very well; the DCQM performs better in unsaturation situation.


---

## Body

## 1. Introduction

IEEE 802.11 Distributed Coordination Function (DCF) [1] has been widely used in mobile ad hoc networks. However, in high diversity node situation, the IEEE 802.11 DCF suffers from many collisions, resulting in low frequency utilization [2].Multichannel MAC protocol can help to share the traffic loads among different channels. Hence, the collisions single-channel MAC protocols suffered from can be alleviated. In fact, IEEE 802.11b and IEEE 802.11a can support 3 and 13 nonoverlapping channels, respectively [2]. This means that designing a multichannel MAC (MMAC) protocol is feasible and desirable in IEEE 802.11-based mobile ad hoc networks.The great challenge of designing MMAC is how to allocate channels to node for transmitting information. And solutions to this problem can be classified into two patterns:(a)
Channel negotiating pattern: channels allocated by negotiating through dedicated control slot or channel.(b)
Channel-hopping pattern: nodes switch channels in a fixed pattern or random mechanism.There are many protocols ([3–15]) that belong to the channel negotiating pattern. In these protocols, some are equipped with at least two transceivers, such as protocols [3, 7, 11–14]. For these protocols, one transceiver is turned to a common control channel that is dedicated for negotiating the channel to be used next. Once the channel is selected, the other transceiver(s) will switch to the negotiated channel for data transmission. These protocols are referred to as the multitransceiver channel negotiating solutions. An undesirable feature of these protocols is high hardware cost. In addition, at one moment, at most one transmission pair can be handled, and the dedicated control transceiver is a bottleneck of the throughput of network. To solve these problems, some are equipped with only one transceiver, such as [4–6, 8–10, 15]. Among them, protocols [5, 6, 9, 15] use a dedicated control channel for control message exchange. In such methods, the dedicated control channel will be either overloaded or underutilized if the capacity of the dedicated control channel and the data channels is not properly distributed. Some other proposals [4, 8, 10] use a common control period, which is similar to the ATIM window concept in IEEE 802.11 power-saving mode (PSM), for nodes to negotiate the data channels. Using either a dedicated control channel or a common control period, these protocols are referred to as the single-transceiver channel negotiating solutions. However, the bottleneck still exists, and no concurrent handshaking is allowed.Different from the channel negotiating pattern, some other solutions utilize the channel-hopping concept to switch among data channels to achieve concurrent handshaking. Similarly, some of channel-hopping pattern protocols are equipped with at least two transceivers, such as protocols [16–18]. However, owing to the high hardware cost and difficulty to be realized in current equipment, we only discuss the single-transceiver protocols in the rest of paper. The protocols [19–21] are equipped with only one transceiver. In these protocols, different nodes have different channel-hopping sequences, and each pair of nodes is able to communicate with each other when they switch to the same channel at the same time slot. In [19], a multichannel protocol called multichannel MAC protocol (McMAC) uses a common linear congruential generator to build each node’s channel-hopping sequence. An asynchronous efficient multichannel MAC protocol (EM-MAC) also adopts the pseudorandom channel-hopping mechanism in [20]. In the slotted seeded channel-hopping protocol (SSCH) [21], a channel-hopping mechanism is proposed such that any two nodes are guaranteed to have a rendezvous once in one cycle. A flaw of these channel-hopping protocols is that they may suffer from the missing receiver problem. This problem frequently occurs, particularly in a heavy-loaded environment [5]. In [2], Chao and Tsai propose a cyclic quorum-based multichannel (CQM) MAC protocol. According to channel-hopping strategy of CQM protocol, based on cyclic quorum system, every channel has the same chance to be accessed. Hence, it can overcome the bottleneck of channel negotiating pattern and the missing receiver problem of channel-hopping pattern.However, as is known to us, the most optimal performance of CQM protocol is not analyzed theoretically yet. And in unsaturation situation, the performance of the fixed channel slot allocation scheme cannot be optimal. Hence, to obtain the optimal performance, we analyze the performance of CQM protocol theoretically based on Markov chain model. And a traffic prediction based dynamic channel slot allocation scheme of CQM protocol is proposed.The rest of this paper is organized as follows. The cyclic quorum system and CQM protocol are introduced in Section2. The Markov chain model and performance analysis of CQM protocol are given in Section 3. The saturation bound is obtained by bird swarm optimal algorithm in Section 4. The traffic prediction based dynamic channel slot allocation scheme of CQM protocol is introduced in Section 5. In addition, the theoretical performance analysis CQM protocol is verified, and the performance comparison between CQM and DCQM protocols is also given in Section 6. The paper is concluded in Section 7.


## 2. Introduction of CQM Protocol

### 2.1. Cyclic Quorum System

Quorum systems have been widely used for MAC protocol designing in wireless networks [22, 23]. And a quorum system can be defined as follows.Given a universal setU={0,…,n-1}, a quorum system Q under U is a collection of nonempty subsets of U, each called a quorum, which satisfies the intersection property(1)G∩H≠ϕ:∀G,H∈Q.There are many quorum systems, such as the cyclic quorum system, the grid quorum system, and the torus quorum system. The cyclic quorum system has the elegant feature of rotation closure property, and it can provide equal opportunity for a node to transmit and to receive. The rotation closure property is as follows:(2)G∩rotateH,i≠⌀:∀G,H∈Q,i∈0,…,n-1where  rotateH,i=j+imod⁡n∣j∈H.A cyclic quorum system can be constructed from a difference set. The definitions of a difference set and a cyclic quorum system are as follows.Given a setD={d1,…,dk}, dk∈Zn, the set D can be a difference set if (3)∀e≠0mod⁡n,∃di-dj=emod⁡nwheredi,dj∈D.Given a difference setD={d1,…,dk},  dk∈Zn, a cyclic quorum Q can be defined as follows:(4)Q=Q0,…,Qn-1,whereQi=d1+i,…,dk+imod⁡n,i=1,…,n.


### 2.2. CQM Protocol

Based on cyclic quorum system, Chao and Tsai propose a cyclic quorum-based multichannel (CQM) MAC protocol [2]. The CQM protocol does not need channel negotiating, so the bottleneck of channel negotiating mechanism can be avoided. In CQM protocol, nodes can communicate with others when they meet at the same channel and same channel slot. And it can provide equal opportunity for nodes to transmit and to receive through the cyclic quorum system.In CQM protocol, time is divided into a series of cycles. Each cycle consists of default channel slots and switching channel slots, numbered from 0 toz-1. The value of z is determined by the integer set from which the adopted difference set is derived. According to [2], CQM system performs better under Z6. In this paper, Z6 is adopted in the analysis of CQM system.LetT denote the channel slot length, to separate with system time slot σ. We assume that the length of channel slot T is long enough to transmit at least one data packet. At default channel slots, a node stays at its default channel, waiting for transmission requests. At switching channel slots, a node may switch to its intended receiver’s default channel. We use a cyclic quorum Gi under Zn to identify a node’s default slots. Specifically, for any node i∈V, where V is the set of nodes in the network, ith node’s default channel (denoted as DCi) and default slots (denoted as DSi) are chosen as follows:(5)DCi=node_IDimod⁡hDSi=Gj,j=node_IDimod⁡z,wherei∈V,where node_IDi is the ID of ith node.Figure1 is an example of CQM operation under Z6 with two channels (numbered from 0 to 1). Nodes 0, 1, and N, with IDs 0, 1, and N, respectively, are within each other’s transmission range. Each node’s default channel and default slots are shown in Figure 1, supposing that we choose the difference set 0,1,3 under Z6 as G0. The marked time slots are default channel slots. The number in each channel slot is the channel that should be switched to.Figure 1
The protocol processing of CQM protocol with two channels.As is shown in Figure1, when a packet arrives at a random time slot, the packet should wait in queue until all preceding packets are transmitted. And then the node looks up its channel-hopping table and checks whether it can meet its destination node at the current channel slot. If they meet each other at the current channel slot, the node can turn into the back-off stage. Otherwise, the node will turn into Wait1 state to wait for the next channel slot available. During back-off stage, the back-off timer of a node is set to a random time according to 802.11 DCF scheme. In this paper, according to CQM protocol, when the channel is occupied by the other nodes or the current channel slot is empty, the back-off timer is assumed to be held to wait for the next channel slot available. And then, the channel slot remaining will be checked when back-off timer reaches zero. If the channel slot remaining is long enough for one packet transmission, the packet will be transmitted. Otherwise, the node should turn into Waiti,03 state to wait for the next channel slot available. Finally, after each successful transmission or after having reached the maximum number of the retransmissions m, if there is a packet to be transmitted in queue, the node enters into checking processing again. Otherwise, the node enters into the idle state. q denotes the probability of having an empty queue.Take Node 0 for example; Table1 shows average channel slots needed between twice meeting in one cycle in the situation that the node is at meeting state and waiting state. And the average meeting slots and waiting slots in one cycle are also shown in Table 1.Table 1
Average channel slots analysis of node 0.
Quorum combinations
Waiting channel slots between two meetings
Channel slots in one cycle
Meetingstate
Waitingstate
Meetingslots
Waitingslots
G
0
+
G
0
1
/
h
4
/
3
h
3
/
h
(
6
h
-
3
)
/
h
G
0
+
G
1
2
7/4
2
4
G
0
+
G
2
2
2
2
4
G
0
+
G
3
6
3
1
5
G
0
+
G
4
3
5/2
2
4
G
0
+
G
5
2
3/2
2
4
Results
E(W_meeting)
E(W_waiting)
E(M_slots)
E(W_slots)
15
h
+
1
/
6
h
129
h
+
16
/
12
h
3
h
+
1
/
2
h
9
h
-
1
/
2
h


## 2.1. Cyclic Quorum System

Quorum systems have been widely used for MAC protocol designing in wireless networks [22, 23]. And a quorum system can be defined as follows.Given a universal setU={0,…,n-1}, a quorum system Q under U is a collection of nonempty subsets of U, each called a quorum, which satisfies the intersection property(1)G∩H≠ϕ:∀G,H∈Q.There are many quorum systems, such as the cyclic quorum system, the grid quorum system, and the torus quorum system. The cyclic quorum system has the elegant feature of rotation closure property, and it can provide equal opportunity for a node to transmit and to receive. The rotation closure property is as follows:(2)G∩rotateH,i≠⌀:∀G,H∈Q,i∈0,…,n-1where  rotateH,i=j+imod⁡n∣j∈H.A cyclic quorum system can be constructed from a difference set. The definitions of a difference set and a cyclic quorum system are as follows.Given a setD={d1,…,dk}, dk∈Zn, the set D can be a difference set if (3)∀e≠0mod⁡n,∃di-dj=emod⁡nwheredi,dj∈D.Given a difference setD={d1,…,dk},  dk∈Zn, a cyclic quorum Q can be defined as follows:(4)Q=Q0,…,Qn-1,whereQi=d1+i,…,dk+imod⁡n,i=1,…,n.


## 2.2. CQM Protocol

Based on cyclic quorum system, Chao and Tsai propose a cyclic quorum-based multichannel (CQM) MAC protocol [2]. The CQM protocol does not need channel negotiating, so the bottleneck of channel negotiating mechanism can be avoided. In CQM protocol, nodes can communicate with others when they meet at the same channel and same channel slot. And it can provide equal opportunity for nodes to transmit and to receive through the cyclic quorum system.In CQM protocol, time is divided into a series of cycles. Each cycle consists of default channel slots and switching channel slots, numbered from 0 toz-1. The value of z is determined by the integer set from which the adopted difference set is derived. According to [2], CQM system performs better under Z6. In this paper, Z6 is adopted in the analysis of CQM system.LetT denote the channel slot length, to separate with system time slot σ. We assume that the length of channel slot T is long enough to transmit at least one data packet. At default channel slots, a node stays at its default channel, waiting for transmission requests. At switching channel slots, a node may switch to its intended receiver’s default channel. We use a cyclic quorum Gi under Zn to identify a node’s default slots. Specifically, for any node i∈V, where V is the set of nodes in the network, ith node’s default channel (denoted as DCi) and default slots (denoted as DSi) are chosen as follows:(5)DCi=node_IDimod⁡hDSi=Gj,j=node_IDimod⁡z,wherei∈V,where node_IDi is the ID of ith node.Figure1 is an example of CQM operation under Z6 with two channels (numbered from 0 to 1). Nodes 0, 1, and N, with IDs 0, 1, and N, respectively, are within each other’s transmission range. Each node’s default channel and default slots are shown in Figure 1, supposing that we choose the difference set 0,1,3 under Z6 as G0. The marked time slots are default channel slots. The number in each channel slot is the channel that should be switched to.Figure 1
The protocol processing of CQM protocol with two channels.As is shown in Figure1, when a packet arrives at a random time slot, the packet should wait in queue until all preceding packets are transmitted. And then the node looks up its channel-hopping table and checks whether it can meet its destination node at the current channel slot. If they meet each other at the current channel slot, the node can turn into the back-off stage. Otherwise, the node will turn into Wait1 state to wait for the next channel slot available. During back-off stage, the back-off timer of a node is set to a random time according to 802.11 DCF scheme. In this paper, according to CQM protocol, when the channel is occupied by the other nodes or the current channel slot is empty, the back-off timer is assumed to be held to wait for the next channel slot available. And then, the channel slot remaining will be checked when back-off timer reaches zero. If the channel slot remaining is long enough for one packet transmission, the packet will be transmitted. Otherwise, the node should turn into Waiti,03 state to wait for the next channel slot available. Finally, after each successful transmission or after having reached the maximum number of the retransmissions m, if there is a packet to be transmitted in queue, the node enters into checking processing again. Otherwise, the node enters into the idle state. q denotes the probability of having an empty queue.Take Node 0 for example; Table1 shows average channel slots needed between twice meeting in one cycle in the situation that the node is at meeting state and waiting state. And the average meeting slots and waiting slots in one cycle are also shown in Table 1.Table 1
Average channel slots analysis of node 0.
Quorum combinations
Waiting channel slots between two meetings
Channel slots in one cycle
Meetingstate
Waitingstate
Meetingslots
Waitingslots
G
0
+
G
0
1
/
h
4
/
3
h
3
/
h
(
6
h
-
3
)
/
h
G
0
+
G
1
2
7/4
2
4
G
0
+
G
2
2
2
2
4
G
0
+
G
3
6
3
1
5
G
0
+
G
4
3
5/2
2
4
G
0
+
G
5
2
3/2
2
4
Results
E(W_meeting)
E(W_waiting)
E(M_slots)
E(W_slots)
15
h
+
1
/
6
h
129
h
+
16
/
12
h
3
h
+
1
/
2
h
9
h
-
1
/
2
h


## 3. Performance Analysis of CQM Protocol

### 3.1. Markov Model of CQM Protocol

Combined with the channel-hopping strategy of CQM protocol and 802.11 DCF, the Markov chain model of CQM protocol is proposed, as is shown in Figure2. We consider the following assumptions for modeling network. (1) The network consists of n nodes moving in the range of transmission distance, and packets are transmitted from sources to destinations directly. (2) A total of h channels are available for every node, and all of them have the same bandwidth. (3) Every node knows the IDs of its one-hop neighbors, and every node is equipped with one-half-duplex transceiver, which is able to switch to any channel dynamically. (4) Every node is time synchronized and uses the IEEE 802.11 DCF (RTS/CTS mode) as MAC protocol. (5) Packets arrive to a node according to a Poisson process with rate λ packets/s. (6) The channel is assumed to be error-free. Packet transmission is considered to be successful if there are no other packets transmissions at the same time.Figure 2
Markov chain model of CQM protocol.According to CQM protocol, each node has the same chance to transmit packet through different channels. So we can take one selected channel of a node into consideration to model the CQM protocol scheme at MAC layer. And then we assume that there aren′=n/h nodes with packets rate λ to content in one selected channel in a random time slot. The model consists of states that a node can reside in. The points C0,C1,C2,C0′,…,Cm′ represent connection points, which are not states.During queuing stage, the arriving packet will wait in buffer, if there are other packets to be transmitted. And if there is no packet in buff, the node will turn into idle state.If the packet is eligible to be transmitted, the node enters into checking stage. The channel-hopping table will be checked firstly. The node can meet its destination node with probabilityPmeeting and turns into Wait1 state to wait for next channel slot available with probability 1-Pmeeting.During back-off stage, we use the tuple(i,k) to represent the different states. i denotes the ith back-off stage, and number i=0,1,…,m′,…,m, and k denotes the value of back-off timer in the range [0,Wi-1] [24]. Wi is the size of the CW at stage i, which can be expressed as follow:(6)Wi=2i∗W0,ifi≤m′2m′∗W0,ifi>m′,where m denotes the maximum number of packet retransmissions before the packet is dropped. According to [25], the default value for m′ is 5 and it is 7 for m.When time slotσ is idle and the current channel slot remaining is sufficient for once back-off timer decrease, the state (i,k) will turn into (i,k-1) with probability Pt_sufficient′. Otherwise, the back-off timer will be held and the node will wait for next channel slot available. According to 802.11 DCF, the packet will be transmitted when node turns into (i,0) states. Different from that, in this model, only if channel slot remaining is long enough for one packet transmission, the packet will be transmitted at (i,0) states. Otherwise, the node will enter into Waiti,03 state to wait for next channel slot available. Pi,k denotes the probability of state (i,k). Pt_success denotes the probability that a node transmits successfully in a random time slot and one selected channel. We use PCi to denote the probability that the node arrives at point Ci.In order to obtain the expression of state-steady probabilities of a node, firstly, we need to expressPi,k in terms of P0,0. According to Figure 2, during back-off stage, we can obtain the following relations:(7)PCi′=Pi,0∗Pt_sufficient+PWaiti,03=Pi,0∗Pt_sufficient+Pi,0∗1-Pt_sufficient=Pi,0,0≤i≤m,Pi,k=Pi,k+1∗Pt_sufficient′+PWaiti,k2=Pi,k+1∗Pt_sufficient′+Pi,k+1∗1-Pt_sufficient′=Pi,k+1,0≤j≤Wi-1,Pi,0=∑u=0wi-1PCi-1′∗1-Pt_successwi=1-Pt_successi∗P0,0,1≤i≤m,∑u=0w0-1PC2∗1w0=PC2,i=0,Pi,k=∑u=0wi-k-1PCi-1′∗1-Pt_successwi=wi-kwi∗1-Pt_successi∗P0,0,1≤i≤m,∑u=0w0-k-1PC2∗1w0=w0-kw0∗PC2=w0-kw0∗P0,0,i=0,where Pt_sufficient and Pt_sufficient′ denote the probability that the remaining channel time is enough for one packet transmission and once back-off timer decrease, respectively. They can be expressed as follows:(8)Pt_sufficient=T-TsT,Pt_sufficient′=T-σT.LetPrs denote the probability that only s nodes out of r nodes transmit packets in a random time slot and one selected channel. Hence, Pt_success can be expressed as follows:(9)Pt_success=Pn′-10=Cn′-10τ01-τn′-1=1-τn′-1,where τ denotes the probability that a node transmits one packet in a random time slot and one selected channel. τ can be expressed as follows:(10)τ=∑i=0mPCi′=∑i=0m1-Pt_successi∗P0,0=α∗P0,0,whereα=1-1-Pt_successm+1Pt_success.Combining (9) with (10), P0,0 can be expressed with Pt_success:(11)P0,0=1-Pt_success1/n′-1α.And then, thePCi can be obtained as follows:(12)PC0=∑i=0m-1PCi′∗Pt_success+PCm′=∑i=0m-11-Pt_successi∗P0,0∗Pt_success+1-Pt_successm∗P0,0=P0,0,(13)PIdle=PC0∗qPtraffic=qPtrafficP0,0,(14)PC1=PC0∗1-q+PIdle∗Ptraffic=PC0=P0,0,(15)PC2=PC1∗Pmeeting+PWait1=PC1∗Pmeeting+PC1∗1-Pmeeting=PC1=P0,0,where Pmeeting denotes the probability that a pair of nodes can meet each other in a random channel slot and a selected channel. According to analysis above, Pmeeting can be expressed as follows:(16)Pmeeting=EM_slots6=3h+112h.LetPWait1, PWaiti,k2, and PWaiti,03 denote the probability of Wait1, Waiti,k2, and Waiti,03 states, respectively. TWait1, TWaiti,k2, and TWaiti,03 denote the time cost at Wait1, Waiti,k2, and Waiti,03 states. According to Figure 2, they can be expressed as follows:(17)PWait1=PC1∗1-Pmeeting=9h-112h∗P0,0,TWait1=EW_waiting∗T=129h+1612h∗T,PWaiti,k2=Wi-k∗1-Pt_successi∗σ∗P0,0WiT,TWaiti,k2=EW_meeting∗T=15h+1∗T6h,PWaiti,03=1-Pt_successi∗P0,0∗TsT,TWaiti,03=Ts2+EW_meeting∗T=15h+1∗T+3hTs6h,where Ptraffic=1-e-λσ denotes the probability of having packet to be transmitted in a random time slot σ when the node is at Idle state. q denotes the probability that there is no packet in the queue of a node after each successful transmission or after having reached the maximum number of the retransmissions m. q can be expressed as follows:(18)q=e-λ∗ESb.And then (13) can be rewritten as follows:(19)PIdle=qPtrafficP0,0=q1-e-λσP0,0,where E[Sb] denotes the average service time of one packet transmission (from the packet leaving the MAC buffer until it is successfully transmitted or reaches the retry limit). According to Figure 2, E[Sb] includes two section: the first one is the average time cost in checking stage (E[TWait1]), and the other is the average time cost in back-off stage(E[Tbackoff]):(20)ESb=ETWait1+ETbackoff.According to Figure2, E[TWait1] can be expressed as follows:(21)ETWait1=TWait1∗PWait1=9h-1∗129h+16∗T144h2∗P0,0.To get the value of all states in Figure2, the average time cost E[Tbackoff] in back-off stage should be obtained firstly. According to Figure 2, E[Tbackoff] can be expressed as follows:(22)ETbackoff=σ-∑i=0m1-Pt_successiWi-12+∑i=0mTS+TWaiti,03∗1-Pt_succicient1-Pt_successiPt_success+∑i=1mTC+TWaiti,03∗1-Pt_succicient∗1-Pt_successiPt_successi+m+11-Pt_successm+1.Combining (6) with (22), E[Tbackoff] can be expressed with Pt_success(23)ETbackoff=σ-21-21-Pt_successm′+1W01-21-Pt_success+2m′1-Pt_successm′+1W01-1-Pt_successm-m′Pt_success-α+TS+15h+1∗T∗TS+3hTS26hTα∗Pt_success+TC+15h+1∗T∗TS+3hTS26hT∗1-Pt_success∗α.Assume(24)β=1-21-Pt_successm′+1W01-21-Pt_success+2m′1-Pt_successm′+1W01-1-Pt_successm-m′Pt_success,γ=15h+1∗T∗TS+3hTS26hT,and then (23) can be rewritten as follows:(25)ETbackoff=σ-2∗β-α+TS+γ∗α∗Pt_success+TC+γ∗1-Pt_success∗α,where σ- denotes the average time between successive counter decrements in back-off stage. The time needed for successive counter decrements includes situations: only one time slot σ′ is needed when all the other nodes have no packet to be transmitted, Ts+σ′ needed when a packet is transmitted successfully by the other nodes, and Tc+σ′ needed when a transmission collision occurs in the other nodes. Let Pσ′, PTs+σ′, and PTc+σ′ denote probabilities of these situations, respectively. Where σ′ denotes the average time cost for once back-off timer decrease when the channel is idle. σ′ can be expressed as follows:(26)σ′=σ∗Pt_sufficient′+TWaiti,k2∗1-Pt_sufficient′=T-σσT+15h+1σ6h.And then, we can get(27)Pσ′=Pn′-10=1-τn′-1,PTs+σ′=Pn′-11=Cn′-11τ1-τn′-2=n′-1τ1-τn′-2,PTc+σ′=1-Pσ′-PTs+σ′=1-1-τn′-1-n′-1τ1-τn′-2.σ
- can be expressed as follows:(28)σ-=σ′∗Pσ′+Ts+σ′∗PTs+σ′+Tc+σ′∗PTc+σ′,where Ts is the time cost for a successful transmission and Tc is the average time the channel is sensed busy by each station during a collision. Let H=PHYhdr+MAChdr be the packet header, and let δ be the propagation delay. Ts and Tc are equal to(29)Ts=DIFS+RTS+CTS+H+EP+ACK+3SIFS+4δ,Tc=DIFS+RTS+CTS+SIFS+δ.Based on this analysis, the value ofq and Pt_success should be obtained before all the state-steady probabilities of a node can be got. Firstly, the relation between them can be expressed based on (18) and (20):(30)q=e-λ′∗ESb=e-λ′∗ETWait1+ETbackoff.In addition, the relation betweenq and Pt_success also can be obtained by using the normalization condition(31)∑i=0m∑k=0wi-1Pi,k+PWait1+PIdle+∑i=0m∑k=1wi-1PWaiti,k2+∑i=0mPWaiti,03=1,1+σT∗β-α2∗P0,0+9h-112h∗P0,0+q1-e-λσ∗P0,0+α∗TsT∗P0,0=1,P0,0∗1+σT∗β-α2+9h-112h+q1-e-λσ+α∗TsT=1.The equation can be expressed as follows:(32)P0,0=11+σ/T∗β-α/2+9h-1/12h+q/1-e-λσ+α∗Ts/T.Equations (30) and (32) are nonlinear and nonconvex. The equation set can be solved using arithmetic solution. And then, all the probabilities of Pi,k, PCi, PIdle, PWait1, PWaiti,k2, and PWaiti,03can be got too.


### 3.2. Throughput Analysis

Now, we will analyze the throughput of CQM protocol. LetS denote the throughput of CQM system. In this paper, we assume the total of h channels is available, and all of them have the same bandwidth. Hence, the throughput of CQM protocol can be expressed as follows:(33)S=∑i=1hS-=h∗ElEslot,where E[l] denotes the average payload size per virtual slot in one selected channel. E[l] can be expressed as follows:(34)El=Pn1∗l=Cn′1τ1-τn′-1∗l=n′τ1-τn′-1∗l.AndE[slot] denotes the virtual slot duration. It contains the duration of an empty slot time σ, the time duration TS due to a successful transmission, and the time duration TC due to a collision, respectively. And then the average slot duration E[slot] can be obtained:(35)Eslot=Pn0∗σ+Pn1∗TS+1-Pn0-Pn1∗TC.Finally, the normalized throughput of CQM protocol can be obtained:(36)S~=Sh∗C=Pn1∗lPn0∗σ+Pn1∗TS+1-Pn0-Pn1∗TC∗C.


### 3.3. Average Packet Transmission Delay Analysis

In this section, we will analyze the expected packet transmission delay at the MAC layer of CQM protocol. Our analysis considers the delayE[Dtr] for a successfully transmitted packet in the case of saturation. E[Dtr] is defined as the time when a packet becomes eligible to be transmitted until it is transmitted successfully. So, E[Dtr] is equal to the back-off service time (E[Sb]) excluding the term corresponding to dropping a packet (E[Tdrop]):(37)EDtr=ESb-ETdrop=ETWait1+ETbackoff-1-Pt_successm+1∗m+1∗Tc+γ+σ-∗∑i=0mWi-12.


### 3.4. Numerical Analysis of CQM Protocol

To show the influence of parameters (n, λ, T, and h) to the performance (E[Dtr] and S) of CQM system obviously, we now present the relationship between them by numerical analysis when h is set to 3. A summary of parameters is shown in Table 2.Table 2
CQM system parameters in numerical analysis.
Packet length
8192 bits
MAC header
272 bits
Physical header (PHY)
128 bits
ACK
112 bits + PHY header
RTS
160 bits + PHY header
CTS
112 bits + PHY header
SIFS
28 us
DIFS
128 us
m
6
m
′
5
Slot duration
50 us
Propagation delay
1 us
Channel bit rate
1 Mbps
Channel number
3The throughput versus node number and packet rate is shown in Figure3, when the channel slot length is set to 100 ms.Figure 3
Throughput versus node number and packet rate withT=100 ms.
(a)
Throughput of CQM system (3D)
(b)
Throughput of CQM system (top view)As is shown in Figure3(a), the throughput increases gradually with the increased node number with a certain packet rate, and it approaches a constant in the end. In a network, with the node number increases, more packets can be transmitted successfully, so the throughput of network increases. However, with the network size become much bigger, more and more nodes transmit packets in one channel with a certain bandwidth, more and more collisions will occur. In the end, the network will reach a balance state, and the throughout will approach a constant. As is similar to the influence of node number, the throughput has the same change trend with the increased packet rate.As is shown in Figure3(b), with the increase of node number and packet rate, the throughput increases gradually. When node number and packet rate reach a bound, the network will turn into saturation state, and throughput reaches its maximum value. In this paper, we call it saturation bound.Figure4 shows the relationship between throughput, node number, and channel slot length. This system consists of 3 channels, and the packet rate is set to 2 packets/s.Figure 4
Throughput versus node number and channel slot length withλ=2.As is shown in Figure4, on the one hand, the throughput increases with the increase of node number in a certain channel slot length, and it approaches a constant value when the network is at saturation state. On the other hand, the throughput changes slowly with the increase of channel slot length in a certain node number.The relation between parameters (n, λ, T) and S can be revealed by numerical analysis. The most maximum throughput can be obtained when parameters (n, λ, T) break through the saturation bound. And then, the change trend of average packet delay with the change of parameters (n, λ, T) can be shown in Figures 5(a) and 5(b).Figure 5
Average packet transmission delay in oversaturation case.
(a)
Average packet transmission delay of CQM system withT=100 ms (3D)
(b)
Average packet transmission delay of CQM system withn=36, λ=8As is shown in Figure5(a), with a given T=100 ms, the average packet delay increases sharply with the increase of node number in oversaturation case. The increased packet rate has little influence on the average packet delay. However, the packet dropping rate will increase sharply with the increase of packet rate in oversaturation case. Figure 5(b) shows that, with the given λ=8 and n=36, the maximum throughput and minimum average packet transmission delay can be obtained when channel slot length is set to 0.1s. That is to say, for a given λ and n, the network can reach the saturation situation only when the channel slot length reaches one certain value.Based on the analysis in this section, for a network with a certain channel slot length, the maximum throughput, minimum average packet delay, and minimum drop rate can be obtained only in the saturation bound case. And we will find the saturation bound of CQM system based on bird swarm algorithm in Section5.


## 3.1. Markov Model of CQM Protocol

Combined with the channel-hopping strategy of CQM protocol and 802.11 DCF, the Markov chain model of CQM protocol is proposed, as is shown in Figure2. We consider the following assumptions for modeling network. (1) The network consists of n nodes moving in the range of transmission distance, and packets are transmitted from sources to destinations directly. (2) A total of h channels are available for every node, and all of them have the same bandwidth. (3) Every node knows the IDs of its one-hop neighbors, and every node is equipped with one-half-duplex transceiver, which is able to switch to any channel dynamically. (4) Every node is time synchronized and uses the IEEE 802.11 DCF (RTS/CTS mode) as MAC protocol. (5) Packets arrive to a node according to a Poisson process with rate λ packets/s. (6) The channel is assumed to be error-free. Packet transmission is considered to be successful if there are no other packets transmissions at the same time.Figure 2
Markov chain model of CQM protocol.According to CQM protocol, each node has the same chance to transmit packet through different channels. So we can take one selected channel of a node into consideration to model the CQM protocol scheme at MAC layer. And then we assume that there aren′=n/h nodes with packets rate λ to content in one selected channel in a random time slot. The model consists of states that a node can reside in. The points C0,C1,C2,C0′,…,Cm′ represent connection points, which are not states.During queuing stage, the arriving packet will wait in buffer, if there are other packets to be transmitted. And if there is no packet in buff, the node will turn into idle state.If the packet is eligible to be transmitted, the node enters into checking stage. The channel-hopping table will be checked firstly. The node can meet its destination node with probabilityPmeeting and turns into Wait1 state to wait for next channel slot available with probability 1-Pmeeting.During back-off stage, we use the tuple(i,k) to represent the different states. i denotes the ith back-off stage, and number i=0,1,…,m′,…,m, and k denotes the value of back-off timer in the range [0,Wi-1] [24]. Wi is the size of the CW at stage i, which can be expressed as follow:(6)Wi=2i∗W0,ifi≤m′2m′∗W0,ifi>m′,where m denotes the maximum number of packet retransmissions before the packet is dropped. According to [25], the default value for m′ is 5 and it is 7 for m.When time slotσ is idle and the current channel slot remaining is sufficient for once back-off timer decrease, the state (i,k) will turn into (i,k-1) with probability Pt_sufficient′. Otherwise, the back-off timer will be held and the node will wait for next channel slot available. According to 802.11 DCF, the packet will be transmitted when node turns into (i,0) states. Different from that, in this model, only if channel slot remaining is long enough for one packet transmission, the packet will be transmitted at (i,0) states. Otherwise, the node will enter into Waiti,03 state to wait for next channel slot available. Pi,k denotes the probability of state (i,k). Pt_success denotes the probability that a node transmits successfully in a random time slot and one selected channel. We use PCi to denote the probability that the node arrives at point Ci.In order to obtain the expression of state-steady probabilities of a node, firstly, we need to expressPi,k in terms of P0,0. According to Figure 2, during back-off stage, we can obtain the following relations:(7)PCi′=Pi,0∗Pt_sufficient+PWaiti,03=Pi,0∗Pt_sufficient+Pi,0∗1-Pt_sufficient=Pi,0,0≤i≤m,Pi,k=Pi,k+1∗Pt_sufficient′+PWaiti,k2=Pi,k+1∗Pt_sufficient′+Pi,k+1∗1-Pt_sufficient′=Pi,k+1,0≤j≤Wi-1,Pi,0=∑u=0wi-1PCi-1′∗1-Pt_successwi=1-Pt_successi∗P0,0,1≤i≤m,∑u=0w0-1PC2∗1w0=PC2,i=0,Pi,k=∑u=0wi-k-1PCi-1′∗1-Pt_successwi=wi-kwi∗1-Pt_successi∗P0,0,1≤i≤m,∑u=0w0-k-1PC2∗1w0=w0-kw0∗PC2=w0-kw0∗P0,0,i=0,where Pt_sufficient and Pt_sufficient′ denote the probability that the remaining channel time is enough for one packet transmission and once back-off timer decrease, respectively. They can be expressed as follows:(8)Pt_sufficient=T-TsT,Pt_sufficient′=T-σT.LetPrs denote the probability that only s nodes out of r nodes transmit packets in a random time slot and one selected channel. Hence, Pt_success can be expressed as follows:(9)Pt_success=Pn′-10=Cn′-10τ01-τn′-1=1-τn′-1,where τ denotes the probability that a node transmits one packet in a random time slot and one selected channel. τ can be expressed as follows:(10)τ=∑i=0mPCi′=∑i=0m1-Pt_successi∗P0,0=α∗P0,0,whereα=1-1-Pt_successm+1Pt_success.Combining (9) with (10), P0,0 can be expressed with Pt_success:(11)P0,0=1-Pt_success1/n′-1α.And then, thePCi can be obtained as follows:(12)PC0=∑i=0m-1PCi′∗Pt_success+PCm′=∑i=0m-11-Pt_successi∗P0,0∗Pt_success+1-Pt_successm∗P0,0=P0,0,(13)PIdle=PC0∗qPtraffic=qPtrafficP0,0,(14)PC1=PC0∗1-q+PIdle∗Ptraffic=PC0=P0,0,(15)PC2=PC1∗Pmeeting+PWait1=PC1∗Pmeeting+PC1∗1-Pmeeting=PC1=P0,0,where Pmeeting denotes the probability that a pair of nodes can meet each other in a random channel slot and a selected channel. According to analysis above, Pmeeting can be expressed as follows:(16)Pmeeting=EM_slots6=3h+112h.LetPWait1, PWaiti,k2, and PWaiti,03 denote the probability of Wait1, Waiti,k2, and Waiti,03 states, respectively. TWait1, TWaiti,k2, and TWaiti,03 denote the time cost at Wait1, Waiti,k2, and Waiti,03 states. According to Figure 2, they can be expressed as follows:(17)PWait1=PC1∗1-Pmeeting=9h-112h∗P0,0,TWait1=EW_waiting∗T=129h+1612h∗T,PWaiti,k2=Wi-k∗1-Pt_successi∗σ∗P0,0WiT,TWaiti,k2=EW_meeting∗T=15h+1∗T6h,PWaiti,03=1-Pt_successi∗P0,0∗TsT,TWaiti,03=Ts2+EW_meeting∗T=15h+1∗T+3hTs6h,where Ptraffic=1-e-λσ denotes the probability of having packet to be transmitted in a random time slot σ when the node is at Idle state. q denotes the probability that there is no packet in the queue of a node after each successful transmission or after having reached the maximum number of the retransmissions m. q can be expressed as follows:(18)q=e-λ∗ESb.And then (13) can be rewritten as follows:(19)PIdle=qPtrafficP0,0=q1-e-λσP0,0,where E[Sb] denotes the average service time of one packet transmission (from the packet leaving the MAC buffer until it is successfully transmitted or reaches the retry limit). According to Figure 2, E[Sb] includes two section: the first one is the average time cost in checking stage (E[TWait1]), and the other is the average time cost in back-off stage(E[Tbackoff]):(20)ESb=ETWait1+ETbackoff.According to Figure2, E[TWait1] can be expressed as follows:(21)ETWait1=TWait1∗PWait1=9h-1∗129h+16∗T144h2∗P0,0.To get the value of all states in Figure2, the average time cost E[Tbackoff] in back-off stage should be obtained firstly. According to Figure 2, E[Tbackoff] can be expressed as follows:(22)ETbackoff=σ-∑i=0m1-Pt_successiWi-12+∑i=0mTS+TWaiti,03∗1-Pt_succicient1-Pt_successiPt_success+∑i=1mTC+TWaiti,03∗1-Pt_succicient∗1-Pt_successiPt_successi+m+11-Pt_successm+1.Combining (6) with (22), E[Tbackoff] can be expressed with Pt_success(23)ETbackoff=σ-21-21-Pt_successm′+1W01-21-Pt_success+2m′1-Pt_successm′+1W01-1-Pt_successm-m′Pt_success-α+TS+15h+1∗T∗TS+3hTS26hTα∗Pt_success+TC+15h+1∗T∗TS+3hTS26hT∗1-Pt_success∗α.Assume(24)β=1-21-Pt_successm′+1W01-21-Pt_success+2m′1-Pt_successm′+1W01-1-Pt_successm-m′Pt_success,γ=15h+1∗T∗TS+3hTS26hT,and then (23) can be rewritten as follows:(25)ETbackoff=σ-2∗β-α+TS+γ∗α∗Pt_success+TC+γ∗1-Pt_success∗α,where σ- denotes the average time between successive counter decrements in back-off stage. The time needed for successive counter decrements includes situations: only one time slot σ′ is needed when all the other nodes have no packet to be transmitted, Ts+σ′ needed when a packet is transmitted successfully by the other nodes, and Tc+σ′ needed when a transmission collision occurs in the other nodes. Let Pσ′, PTs+σ′, and PTc+σ′ denote probabilities of these situations, respectively. Where σ′ denotes the average time cost for once back-off timer decrease when the channel is idle. σ′ can be expressed as follows:(26)σ′=σ∗Pt_sufficient′+TWaiti,k2∗1-Pt_sufficient′=T-σσT+15h+1σ6h.And then, we can get(27)Pσ′=Pn′-10=1-τn′-1,PTs+σ′=Pn′-11=Cn′-11τ1-τn′-2=n′-1τ1-τn′-2,PTc+σ′=1-Pσ′-PTs+σ′=1-1-τn′-1-n′-1τ1-τn′-2.σ
- can be expressed as follows:(28)σ-=σ′∗Pσ′+Ts+σ′∗PTs+σ′+Tc+σ′∗PTc+σ′,where Ts is the time cost for a successful transmission and Tc is the average time the channel is sensed busy by each station during a collision. Let H=PHYhdr+MAChdr be the packet header, and let δ be the propagation delay. Ts and Tc are equal to(29)Ts=DIFS+RTS+CTS+H+EP+ACK+3SIFS+4δ,Tc=DIFS+RTS+CTS+SIFS+δ.Based on this analysis, the value ofq and Pt_success should be obtained before all the state-steady probabilities of a node can be got. Firstly, the relation between them can be expressed based on (18) and (20):(30)q=e-λ′∗ESb=e-λ′∗ETWait1+ETbackoff.In addition, the relation betweenq and Pt_success also can be obtained by using the normalization condition(31)∑i=0m∑k=0wi-1Pi,k+PWait1+PIdle+∑i=0m∑k=1wi-1PWaiti,k2+∑i=0mPWaiti,03=1,1+σT∗β-α2∗P0,0+9h-112h∗P0,0+q1-e-λσ∗P0,0+α∗TsT∗P0,0=1,P0,0∗1+σT∗β-α2+9h-112h+q1-e-λσ+α∗TsT=1.The equation can be expressed as follows:(32)P0,0=11+σ/T∗β-α/2+9h-1/12h+q/1-e-λσ+α∗Ts/T.Equations (30) and (32) are nonlinear and nonconvex. The equation set can be solved using arithmetic solution. And then, all the probabilities of Pi,k, PCi, PIdle, PWait1, PWaiti,k2, and PWaiti,03can be got too.


## 3.2. Throughput Analysis

Now, we will analyze the throughput of CQM protocol. LetS denote the throughput of CQM system. In this paper, we assume the total of h channels is available, and all of them have the same bandwidth. Hence, the throughput of CQM protocol can be expressed as follows:(33)S=∑i=1hS-=h∗ElEslot,where E[l] denotes the average payload size per virtual slot in one selected channel. E[l] can be expressed as follows:(34)El=Pn1∗l=Cn′1τ1-τn′-1∗l=n′τ1-τn′-1∗l.AndE[slot] denotes the virtual slot duration. It contains the duration of an empty slot time σ, the time duration TS due to a successful transmission, and the time duration TC due to a collision, respectively. And then the average slot duration E[slot] can be obtained:(35)Eslot=Pn0∗σ+Pn1∗TS+1-Pn0-Pn1∗TC.Finally, the normalized throughput of CQM protocol can be obtained:(36)S~=Sh∗C=Pn1∗lPn0∗σ+Pn1∗TS+1-Pn0-Pn1∗TC∗C.


## 3.3. Average Packet Transmission Delay Analysis

In this section, we will analyze the expected packet transmission delay at the MAC layer of CQM protocol. Our analysis considers the delayE[Dtr] for a successfully transmitted packet in the case of saturation. E[Dtr] is defined as the time when a packet becomes eligible to be transmitted until it is transmitted successfully. So, E[Dtr] is equal to the back-off service time (E[Sb]) excluding the term corresponding to dropping a packet (E[Tdrop]):(37)EDtr=ESb-ETdrop=ETWait1+ETbackoff-1-Pt_successm+1∗m+1∗Tc+γ+σ-∗∑i=0mWi-12.


## 3.4. Numerical Analysis of CQM Protocol

To show the influence of parameters (n, λ, T, and h) to the performance (E[Dtr] and S) of CQM system obviously, we now present the relationship between them by numerical analysis when h is set to 3. A summary of parameters is shown in Table 2.Table 2
CQM system parameters in numerical analysis.
Packet length
8192 bits
MAC header
272 bits
Physical header (PHY)
128 bits
ACK
112 bits + PHY header
RTS
160 bits + PHY header
CTS
112 bits + PHY header
SIFS
28 us
DIFS
128 us
m
6
m
′
5
Slot duration
50 us
Propagation delay
1 us
Channel bit rate
1 Mbps
Channel number
3The throughput versus node number and packet rate is shown in Figure3, when the channel slot length is set to 100 ms.Figure 3
Throughput versus node number and packet rate withT=100 ms.
(a)
Throughput of CQM system (3D)
(b)
Throughput of CQM system (top view)As is shown in Figure3(a), the throughput increases gradually with the increased node number with a certain packet rate, and it approaches a constant in the end. In a network, with the node number increases, more packets can be transmitted successfully, so the throughput of network increases. However, with the network size become much bigger, more and more nodes transmit packets in one channel with a certain bandwidth, more and more collisions will occur. In the end, the network will reach a balance state, and the throughout will approach a constant. As is similar to the influence of node number, the throughput has the same change trend with the increased packet rate.As is shown in Figure3(b), with the increase of node number and packet rate, the throughput increases gradually. When node number and packet rate reach a bound, the network will turn into saturation state, and throughput reaches its maximum value. In this paper, we call it saturation bound.Figure4 shows the relationship between throughput, node number, and channel slot length. This system consists of 3 channels, and the packet rate is set to 2 packets/s.Figure 4
Throughput versus node number and channel slot length withλ=2.As is shown in Figure4, on the one hand, the throughput increases with the increase of node number in a certain channel slot length, and it approaches a constant value when the network is at saturation state. On the other hand, the throughput changes slowly with the increase of channel slot length in a certain node number.The relation between parameters (n, λ, T) and S can be revealed by numerical analysis. The most maximum throughput can be obtained when parameters (n, λ, T) break through the saturation bound. And then, the change trend of average packet delay with the change of parameters (n, λ, T) can be shown in Figures 5(a) and 5(b).Figure 5
Average packet transmission delay in oversaturation case.
(a)
Average packet transmission delay of CQM system withT=100 ms (3D)
(b)
Average packet transmission delay of CQM system withn=36, λ=8As is shown in Figure5(a), with a given T=100 ms, the average packet delay increases sharply with the increase of node number in oversaturation case. The increased packet rate has little influence on the average packet delay. However, the packet dropping rate will increase sharply with the increase of packet rate in oversaturation case. Figure 5(b) shows that, with the given λ=8 and n=36, the maximum throughput and minimum average packet transmission delay can be obtained when channel slot length is set to 0.1s. That is to say, for a given λ and n, the network can reach the saturation situation only when the channel slot length reaches one certain value.Based on the analysis in this section, for a network with a certain channel slot length, the maximum throughput, minimum average packet delay, and minimum drop rate can be obtained only in the saturation bound case. And we will find the saturation bound of CQM system based on bird swarm algorithm in Section5.


## 4. Bird Swarm Algorithm Based Saturation Bound

In this section, we will find the saturation bound of CQM system. According to analysis in Section3, the best performance of CQM system can be obtained when the network is in saturation bound case. In this way, the problem can be considered to be an optimization problem. The goal is to find pairs of value of n and λ in saturation bound case with a certain T.For this optimization problem, to get the less average packet transmission delay and less drop rate under the situation with the most maximum throughput, we set the objective function as follows:(38)F=S~∗1000+EDtr+λ.And the constraint conditions are as follows:(39)n∈Z;λ>00<Pt_success≤1;0<q≤1.According to (38) and (39), this optimization problem is nonlinear and nonconvex. To attack this optimization problem, bird swarm algorithm (BSA) is adopted.BSA has elegant properties of effectiveness, superiority, and stability to solve nonlinear and nonconvex problem, proposed by Meng et al. in 2015 [26]. It is based on the three kinds of behaviors of bird: foraging behavior, vigilance behavior, and flight behavior. The BSA concludes four search strategies associated with five simplified rules.(a) Foraging Behavior. Each bird searches for food according to its experience and the swarms’ experience. This behavior can be expressed as follows:(40)xi,jt+1=xi,jt+pi,j-xi,jt×Cog×rand0,1+gj-xi,jt×Soc×rand0,1,where xi,jt denotes the position of the ith bird at time step t. rand0,1 denotes independent uniformly distributed numbers in (0,1). Cog and Soc are two positive numbers, which can be, respectively, called cognitive and social accelerated coefficients. pi,j denotes the best previous position of the ith bird and gi denotes the best previous position shared by the swarm.(b) Vigilance Behavior.Birds would try to move to the centre of swarm, and they would inevitably compete with each other. Thus, each bird would not directly move towards the centre of the swarm. These motions can be formulated as follows:(41)xi,jt+1=xi,jt+A1meanj-xi,jt×rand0,1+A2pk,j-xi,jt×rand-1,1,A1=a1×exp-pFitisumFit+ε×N,A2=a2×exppFiti-pFitkpFitk-pFiti+εpFiti×NsumFit+ε,where k is a positive integer, which is randomly chosen between 1 and N. a1 and a2 are two positive constants in [0,2]. pFiti denotes the ith bird’s best fitness value and sumFit represents the sum of the swarms’ best fitness value. meanj denotes the jth element of the average position of the whole swarm. And ε is the smallest constant in the computer.(c) Flight Behavior. Birds may fly to another site in response to predation threat, foraging, or any other reasons. The behaviors of the producers and scroungers can be described mathematically as follows, respectively:(42)xi,jt+1=xi,jt+randn0,1×xi,jt,xi,jt+1=xi,jt+xk,jt-xi,jt×FL×rand0,1,where randn0,1 denotes Gaussian distributed random number with mean 0 and standard deviation 1. FL means that the scrounger would follow the producer to search for food.Based on BSA algorithm, for a certain channel slot lengthT, we can get the tuple (n,λ) at the saturation bound. The parameter values of BSA algorithm in this section are given in Table 3.Table 3
The parameter values of the BSA algorithm.
Parameters
C
S
a
1
a
2
FL
FQ
T
N
Values
1.5
1.5
1
1
F
L
∈
0.5,0.9
3
50
100In this section, the channel slot lengthT is selected in range of [0.01,1]. And Figure 6(a) shows the results of BSA algorithm with 3 channels. Figure 6(b) is the smooth result of Figure 6(a).Figure 6
The saturation bound results obtained by BSA algorithm.
(a)
The discrete results of BSA algorithm (3D)
(b)
The smooth results of BSA algorithm (3D)The surface in Figure6(b) can denote the saturation bound of CQM system obviously. The point on the surface denotes one possible tuple (n,λ,T) in the saturation bound case. As is shown in Figure 6(b), the packet rate changes against the changes of node number with a certain channel slot.WhenT is set to 100 ms, the relationship between node number and packet rate for different channel number in the saturation bound case can be illustrated in Figure 7. And the normalized throughput for different node number with λ=8 can be shown in Figure 8.Figure 7
The saturation bound of CQM system with different channel number.Figure 8
The prediction model of WNN.As is shown in Figure7, in saturation bound case, the node number decreases with the increase of packet rate with T=100 ms for different channel number. And the node number needed increase with the increase of channel number in a certain packet rate. That is to say, only when the system load is larger than capacity of channel, the network can reach the saturation bound state.


## 5. Traffic Prediction Based DCQM Protocol

According to the analysis in Section4, the accurate performance of CQM MAC protocol is obtained. The metrics (throughput and average packet transmission delay) are calculated in performance analysis, with respect to node number, packet rate, channel slot length, and channel number.In CQM protocol, owing to its equal opportunity for nodes to transmit and to receive, the optimal performance of CQM protocol can be obtained in saturation bound situation.However, in unsaturation situation, in a random time slot, some nodes have packets to be transmitted, while others have no packet to be transmitted. In this situation, the channel slots can not be utilized effectively, due to the fixed slot allocation scheme of CQM protocol.To get the optimal performance in both unsaturation and saturation situations, a dynamic time slot allocation scheme of CQM protocol is proposed, based on traffic prediction. In traffic prediction slot, each node predicts the real time arrival trafficWtra by wavelet neural network. And then, in allocation slot, the next channel slot is allocated according to the predicted traffic of network.


### 5.1. The Prediction Model of Wavelet Neural Network

By contrast with the traditional neural network, WNN shows a higher accuracy, faster convergence, and better fault tolerance to complex nonlinear, uncertain, and unknown system. Wavelet neural network takes the topological structure of BP neural network as the foundation and selects the Morlet wavelet basis function as the transfer function of the hidden layer [27, 28]. As a feed-forward network, BP neural network includes the forward propagation of signal and the backpropagation of error. While the network is in the training and learning process, the weight is continuously adjusted to obtain the minimum total error which is relevant to the appropriate output of the network. The k-m-1 prediction model of WNN is shown in Figure 8.As is shown in Figure8, where xi, i=1,2,…,k, is the input parameter, x^k+1 is the predicted output value in k+1 moment, wij is the layer weight from input layer to hidden layer, and wjk is the layer weight from hidden layer to output layer, where m denotes the node number in hidden layer; a is the expansion parameter of the wavelet function; b is the translation parameter of the wavelet function. The Morlet wavelet basis function can extract the amplitude and phase information of the analyzed signal. Here the Morlet wavelet basis function as the activation function is shown as follows:(43)fx=cos⁡1.75xexp⁡-x22.The wavelet neural network adopts the gradient descent algorithm [29] to correct the connection weight. The error function E=(xk+1-x^k+1) is used to correct the connection weight, so as to minimize the network error.


### 5.2. The Dynamic Time Slot Allocation Scheme

To get the optimal performance in both unsaturation and saturation situation, the DCQM protocol is proposed. Based on CQM protocol and WNN, the traffic prediction slot and allocation slot are added in CQM protocol. Figure10 is an example of DCQM operation under Z6 with two channels (numbered from 0 to 1). Nodes 0, 1, and N, with IDs 0, 1, and N, respectively, are within each other’s transmission range. The protocol processing of DCQM protocol is shown in Figure 9.Figure 9
The protocol processing of DCQM protocol with two channels.Figure 10
The relationship betweenPallo_switch and rtraffic.As is shown in Figure9, the traffic prediction slot and allocation slot are added in front of each channel slot. In the end of a channel slot, number of packets transmitted in channel slot and that in the former channel slots are sent to WNN prediction processing. In traffic prediction slot, the predicted traffic to be transmitted in next channel slot of each node can be obtained. And during the allocation slot, if the predicted traffic is 0, the next channel slot is turned to default slot. Otherwise, nodes will broadcast their predicted traffic in their current channel in a random slot. Each node can get the predicted traffic of nodes in same channel, which can denote the traffic of network. And then, the next channel slot of each node can be allocated, according to one judgment criteria.According to analysis of Figure9, the judgment criteria are the key to allocate the channel slot. To utilize the channel efficiently, the switching channel slot should be preferentially allocated to the nodes that having packets to be transmitted. However, when more and more nodes have packets to be transmitted, if all of them are allocated to switching channel slot, the problem of missing destination node exists. To avoid this problem, the probability Pallo_switch that the switching channel slot is allocated to a node is introduced. And let rtraffic denote the ratio of busy node number to network node number. And Pallo_switch should meet the conditions as follows:(44)Pallo_switch∝1rtraffic,0<rtraffic<1=1,rtrafficis  small  enough=0,rtrafficis  big  enough.As is shown in (44), Pallo_switch is inversely proportional to rtraffic. And rtraffic is obtained through broadcast in allocation slot. After traffic prediction slot, each node obtained their predicted packet number by WNN algorithm. During allocation slot, the nodes that having packets to be transmitted broadcast their predicted packet number in random slot. In this way, each node can obtain the approximate rtraffic of network. And then, each node will turn to switching channel slot according to corresponding Pallo_switch.To obtain the optimalPallo_switch that meets the condition in (44), lots of Monte Carlo simulations are adopted, with h=3,5,7, and 60 nodes considered. For one unsaturation situation (rtraffic∈[0.1,1]), lots of value of Pallo_switch∈[0.01,1] are considered. The optimal Pallo_switch is obtained when the throughput of network reaches its maximum. The relationship between Pallo_switch and rtraffic is revealed in Figure 10.As is shown in Figure10, Pallo_switch is inversely proportional to rtraffic, which meets the condition in (44). And for the same rtraffic, Pallo_switch increases with the increase of channel number. With more channel numbers, the probability that nodes meet their destination nodes becomes bigger. And the utilization rate of frequency increases with the increase of channel number.


## 5.1. The Prediction Model of Wavelet Neural Network

By contrast with the traditional neural network, WNN shows a higher accuracy, faster convergence, and better fault tolerance to complex nonlinear, uncertain, and unknown system. Wavelet neural network takes the topological structure of BP neural network as the foundation and selects the Morlet wavelet basis function as the transfer function of the hidden layer [27, 28]. As a feed-forward network, BP neural network includes the forward propagation of signal and the backpropagation of error. While the network is in the training and learning process, the weight is continuously adjusted to obtain the minimum total error which is relevant to the appropriate output of the network. The k-m-1 prediction model of WNN is shown in Figure 8.As is shown in Figure8, where xi, i=1,2,…,k, is the input parameter, x^k+1 is the predicted output value in k+1 moment, wij is the layer weight from input layer to hidden layer, and wjk is the layer weight from hidden layer to output layer, where m denotes the node number in hidden layer; a is the expansion parameter of the wavelet function; b is the translation parameter of the wavelet function. The Morlet wavelet basis function can extract the amplitude and phase information of the analyzed signal. Here the Morlet wavelet basis function as the activation function is shown as follows:(43)fx=cos⁡1.75xexp⁡-x22.The wavelet neural network adopts the gradient descent algorithm [29] to correct the connection weight. The error function E=(xk+1-x^k+1) is used to correct the connection weight, so as to minimize the network error.


## 5.2. The Dynamic Time Slot Allocation Scheme

To get the optimal performance in both unsaturation and saturation situation, the DCQM protocol is proposed. Based on CQM protocol and WNN, the traffic prediction slot and allocation slot are added in CQM protocol. Figure10 is an example of DCQM operation under Z6 with two channels (numbered from 0 to 1). Nodes 0, 1, and N, with IDs 0, 1, and N, respectively, are within each other’s transmission range. The protocol processing of DCQM protocol is shown in Figure 9.Figure 9
The protocol processing of DCQM protocol with two channels.Figure 10
The relationship betweenPallo_switch and rtraffic.As is shown in Figure9, the traffic prediction slot and allocation slot are added in front of each channel slot. In the end of a channel slot, number of packets transmitted in channel slot and that in the former channel slots are sent to WNN prediction processing. In traffic prediction slot, the predicted traffic to be transmitted in next channel slot of each node can be obtained. And during the allocation slot, if the predicted traffic is 0, the next channel slot is turned to default slot. Otherwise, nodes will broadcast their predicted traffic in their current channel in a random slot. Each node can get the predicted traffic of nodes in same channel, which can denote the traffic of network. And then, the next channel slot of each node can be allocated, according to one judgment criteria.According to analysis of Figure9, the judgment criteria are the key to allocate the channel slot. To utilize the channel efficiently, the switching channel slot should be preferentially allocated to the nodes that having packets to be transmitted. However, when more and more nodes have packets to be transmitted, if all of them are allocated to switching channel slot, the problem of missing destination node exists. To avoid this problem, the probability Pallo_switch that the switching channel slot is allocated to a node is introduced. And let rtraffic denote the ratio of busy node number to network node number. And Pallo_switch should meet the conditions as follows:(44)Pallo_switch∝1rtraffic,0<rtraffic<1=1,rtrafficis  small  enough=0,rtrafficis  big  enough.As is shown in (44), Pallo_switch is inversely proportional to rtraffic. And rtraffic is obtained through broadcast in allocation slot. After traffic prediction slot, each node obtained their predicted packet number by WNN algorithm. During allocation slot, the nodes that having packets to be transmitted broadcast their predicted packet number in random slot. In this way, each node can obtain the approximate rtraffic of network. And then, each node will turn to switching channel slot according to corresponding Pallo_switch.To obtain the optimalPallo_switch that meets the condition in (44), lots of Monte Carlo simulations are adopted, with h=3,5,7, and 60 nodes considered. For one unsaturation situation (rtraffic∈[0.1,1]), lots of value of Pallo_switch∈[0.01,1] are considered. The optimal Pallo_switch is obtained when the throughput of network reaches its maximum. The relationship between Pallo_switch and rtraffic is revealed in Figure 10.As is shown in Figure10, Pallo_switch is inversely proportional to rtraffic, which meets the condition in (44). And for the same rtraffic, Pallo_switch increases with the increase of channel number. With more channel numbers, the probability that nodes meet their destination nodes becomes bigger. And the utilization rate of frequency increases with the increase of channel number.


## 6. Performance Evaluation

To verify our analytical results, we compared analytic results with simulation results obtained from Qualnet simulator. In addition, the performance of CQM and DCQM protocols is also compared through Qualnet simulator. Qualnet simulator is the only parallel and message level network simulation tool, developed by Scalable Networks Technologies. It has the faster running speed, higher accuracy, and better extensibility and is suitable for development and simulation of ad hoc network and wireless sensor networks.In our simulations, nodes are uniformly placed in an area of 170 m × 170 m. The transmission range of a node is 250 m. In this way, all nodes can stay in the transmission range of others. A node keeps a separate FIFO queue for each of its neighbors. Each node may act as a sender where the destination is chosen from its one-hop neighbors. The packet rate is selected in [2, 6]. And the channel slot is set to 100 ms. To get the performance of different channel number, every node is equipped with several interfaces. The interface can be assumed to be different channels, and the CQM channel-hopping strategy is used in our simulations. The number of interface is set to 3, 5, and 7. The system parameters are the same as the numerical analysis in Section 3.Firstly, we will verify the saturation bound of analysis results. Figure11 shows results comparison between numerical analysis and simulation when λ is set to 2, 3, 4, 5, 6, 7, and 8.Figure 11
The comparison between analysis results and simulation results with different channel number.As is shown in Figure11, the numerical analysis results can be verified by simulating. In addition, the more nodes can be accommodated with the increase of channel number. It can be verified that the multichannel system can perform better than the single system in high diversity node situation.And then, we present the aggregate throughput between the CQM and proposed DCQM protocol as shown in Figure12. The simulation parameters of DCQM protocol are the same as that of the CQM protocol. In addition, for DCQM, Tprediction and Tallocation denote the time in the traffic prediction stage and allocation stage, respectively. In this simulation, Tprediction is set to 1ms, and the Tallocation is set to 5 ms. Each traffic flow in the network uses the constant bit rate (CBR) traffic model, the packet size is 1024 bytes, and the packet rate is set to 8.Figure 12
The performance comparison between CQM and DCQM protocol.As is shown in Figure12, for CQM and DCQM protocols, with different channel number, the normalized throughput increases with the increase of packet rate. And then, it reaches its maximum value when node number reaches one certain value. Finally, it decreases with the increase of node number gradually. In addition, in unsaturation situation, the normalized throughput of DCQM is bigger than that of CQM protocol. This is because the utilization of frequency increases due to dynamic channel slot allocation. And in saturation situation, the performance of CQM protocol is slightly better than DCQM protocol. For DCQM protocol, in saturation situation, Pallo_switch is almost 0, and the channel slot allocation is the same as CQM protocol. However, the additional overhead is needed in DCQM protocol because of the additional traffic prediction slot Tprediction and allocation slot Tallocation.


## 7. Conclusions

IEEE 802.11 DCF suffers from many collisions in high diversity node situation. Multichannel MAC protocol can help to share the traffic loads among different channels. And the CQM protocol performed better among MMAC protocols with only one transceiver. However, the performance of CQM protocol is not analyzed theoretically. And the performance is not optimal for the fixed channel slot allocation scheme in unsaturation situation.In this paper, a Markov chain model is proposed to analyze the performance of CQM protocol theoretically. The throughput and average packet transmission delay of CQM system are revealed too. And the saturation bound of CQM protocol is obtained based on BSA algorithm. In addition, to obtain the optimal performance of CQM protocol in unsaturation situation, a traffic prediction based dynamic channel slot allocation scheme of CQM protocol is proposed based on WNN prediction model. In the end, the performance theoretical analysis of CQM protocol is verified by simulating on Qualnet platform. And the performance comparison of CQM and DCQM protocol is simulated too. The results show that the simulation results and analytical results match very well, and the DCQM protocol performs better than CQM protocol in unsaturation situation.



---

*Source: 8580913-2017-09-28.xml*