# An Efficient SS-MAC Protocol for IEEE 802.15.4-Based WSNs of Cluster Tree Topology
## 3 The Proposed SS-MAC Protocol
### Setup Phase (SP)
#### 3.2.4. Data Collection Period (DCP)  
In DCP, each member node receives a data slot announcement (DS_ANN) message from its CH, which informs the number and start time of the data slot allocated. Each CH utilizes its private channel to collect data from its member nodes in a TDMA manner. The TDMA mechanism within cluster units and the FDMA mechanism between cluster units effectively avoid interference between member nodes in the network. We improved the knapsack algorithm proposed in reference [3] to determine the number of slots and order allocated to each member node. 1. DS_ANN message  
Taking a cluster with four member nodes as an example, Figure 5 shows the frame structure of the DS_ANN message. The payload portion includes the following: (1) The number of nodes that have allocated slots (1 byte). It is also the length of the node ID list; (2) The node ID list. Each byte of this field indicates an ID (short address) of member nodes. Later, member nodes sequentially send data packets in the order of the list; (3) Slot allocation list. This field indicates the number of slots allocated to each node, and each 1 byte of field corresponds to the node ID list. If a CH allocates data slots for \(N\) nodes, the DS_ANN message length is \(3N+5\) bytes. If the CAP duration set by the network is \(K\) unit slots, the start time of DS_ANN can be calculated as \(ADS\_ST=CAP\_ST+K\times T_{cap}^{u}\). 2. Knapsack optimization algorithm  
A knapsack optimization algorithm is employed by CHs to allocate data slots for member nodes. Algorithm 1 is designed to select the maximum node number with the maximum slot utilization. The protocol requires a node to transmit all of its data as a whole,  
Figure 5. Structure of DS_ANN message. so the Algorithm 1 is a 0-1 knapsack algorithm. Algorithm 1 assumes that the number of slots requested by a node is the same as its weight. Suppose there are \(n\) member nodes requesting data slots, the number of slots requested by the \(i\)th node is \(W_{i}\), and the total available slots that CH can allocate is \(W\). The basic thought of Algorithm 1 is:  
1. If the total number of requested slots is less than or equal to \(W\), that is, \(W_{1}+W_{2}+\cdots+W_{n}\leq W\), the output of Algorithm 1 is \(C[n,W]\). CH can allocate slots as requests, but the order of transmission is optimized by Algorithm 2. 2. If the total number of requested slots is greater than \(W\), that is, \(W_{1}+W_{2}+\cdots+W_{n}>W\), CH cannot meet the data slot requests of all nodes, Algorithm 1 is implemented to provide an optimal slot allocation scheme \(C[i,W]\). ```
1:\(n\): Total number of node requesting slots
2:\(\omega_{i}\): Number of slots that requested by \(i_{th}\) node
3:\(W\): Max number of slots that can be allocated
4:\(\omega\): Current slot, its value is the element of array \(\omega=\langle\omega_{1},\omega_{2},\cdots,\omega_{n}\rangle\)
5:\(C[i,\omega]\): Optimal value of Knapsack algorithm
6:for\(\omega=0\) to \(W\)do
7:\(C[0,\omega]=0\); //Initialize row 1 with 0
8:
9:endfor
10:for\(i=1\) to \(n\)do
11:\(C[i,0]=0\); //Initialize column 1 with 0
12:for\(i=1\) to \(n\)do
13:if\(\omega_{i}\leq\omega\)then
14:if\(\omega_{i}+C[i-1,\omega-\omega_{i}]>C[i-1,\omega]\)then
15:\(C[i,\omega]=\omega_{i}+C[i-1,\omega-\omega_{i}]\);
16:else
17:\(C[i,\omega]=C[i-1,\omega]\);
18:endif
19:else
20:\(C[i,\omega]=C[i-1,\omega]\);
21:endif
22:endfor
23:endfor
24:return\(C[n,W]\);
```  
**Algorithm 1** SS-MAC Knapsack optimization algorithm. Algorithm 2 is designed to determine the order in which member nodes send data. CH processes the node with the least requesting slots first. All member nodes are sorted in ascending order based on the number of requesting slots. If multiple nodes have the same number of requested slots, they are sorted by their IDs from small to large. The nodes \(N_{1}\) to \(N_{6}\) in Figure 4 are a typical case of using the knapsack optimization algorithm.