## 3 P-MAC Design Integrated with Routing
### Grade Division and Schedule Assignment (GDSA)  
Before starting data transmission, each node need to find a grade it belongs to, and choose a schedule for periodically listening and sleeping. This is implemented by operating the _GDSA_ mechanism at the network layer of each node.  
GDSA is initiated from the sink. In _GDSA_, each node maintains grade information (denoted by \(G_{n}\)) with an initial value of \(-1\), except that the sink's grade is zero (\(G_{n}=0\)) at all times. The sink first chooses a schedule according to its grade (the schedule choosing rule will be introduced in detail in Section 3.5). Then it generates a GRADE message containing a field denoted by \(G_{m}\). After setting \(G_{m}\) to one, the sink broadcasts this message. A node receiving a GRADE message with \(G_{m}=i\) sets its grade to \(i\) (\(G_{n}=i\)), chooses a schedule corresponding with its grade, and rebroadcasts the message after increasing \(G_{m}\) by one, unless it has already joined an equal or a lower grade. The pseudo-code of the algorithm used by a node for processing the received GRADE message is shown in Algorithm 1.  
```
1:if\(G_{n}<0\)then
2:\(G_{n}\gets G_{m}\)
3: choose a corresponding schedule
4:\(G_{m}\gets G_{m}+1\)
5: rebroadcast the GRADE message
6:elseif\(G_{n}>G_{m}\)then
7:\(G_{n}\gets G_{m}\)
8: update the node's schedule
9:\(G_{m}\gets G_{m}+1\)
10: rebroadcast the GRADE message
11:else
12: discard the GRADE message
13:endif
```  
**Algorithm 1**_GDSA_: processing the received GRADE message.  
After the grade division using the above scheme, the whole network is divided into several annular grades similar to concentric circles with the center at the sink, as shown in Figure 1(a). But this is not absolute. For example, if node \(A\) and \(A^{\prime}\) do not exist, the network may be divided into the formation shown in Figure 1(b).  
As stated above, each node simultaneously establishes a periodical sleep/wakeup schedule according to its grade information during the grade division process. Those nodes in the same grade keep the same schedule, but schedules are staggered between two adjacent grade nodes. Suppose a node is in grade \(i\) (\(i>0\)), it repeatedly experiences three periods: receiving data from the (\(i\)+1)th grade node (the _RECEIVE DATA_ period), sending data to the (\(i\)-1)th grade node (the _SEND DATA_ period), and sleeping (the _SLEEP_ period). If the upper grade nodes are in the _SEND DATA_ period, their adjacent lower grade nodes must be in the _RECEIVE DATA_ period (the duration of each period will be analyzed in Section 3.4). Thereby, data frames can be forwarded continuously in a pipeline way from the source node to the sink, thus making the delivery latency acceptable. Those adjacent nodes in the same grade contend with each other for the shared medium while those in different grades cooperate with each other for data transmission.  
The pipelining concept cited in this paper is defined as follows:  
**Definition 1** (Pipelining): _In duty-cycling MAC protocols, a node generally can complete receiving a data frame from one of its upstream nodes and then sending this data frame to one of its downstream nodes within one cycle. This is called pipeline data transmission._