# A Credit-Based Congestion-Aware Incentive Scheme for DTNs
## 4 A Credit-Based Congestion-Aware Incentive Scheme
### Check and Punishment Mechanism  
If a message is discarded deliberately, the misbehavior node must be the last forwarding node on the forwarding path. In order to check the misbehavior node, TTP needs the message forwarding path information. To achieve this, when sending node \(N_{S}\) encounters a forwarding node \(N_{1}\) with smaller delivery delay, they will create a forwarding ticket as in Figure 4.  
In the forwarding ticket, _MessageID_ is the message identifier; \(N_{S}\) and \(N_{D}\) are the node identifiers of the message sending node and receiving node, i.e., destination node, respectively; _Credit_ is the most credits to be paid for a successfully delivered message, as in Equation (3); TTL is the message lifetime; \(t_{gen}\) is the message generation time; \(Path\) is the message forwarding path; \(t_{N_{s}-N_{1}}\) is the time when nodes \(N_{S}\) and \(N_{1}\) meet; \(Sig_{NS}\) and \(Sig_{NI}\) are digital signatures of nodes \(N_{S}\) and \(N_{1}\), respectively;  
Figure 4: Forwarding ticket.  
Figure 3: CBCAIS overview.  
\(EK_{NS}\) is the private key of node \(N_{S}\); and \(H\) is the hash function to generate a summary to ensure the message integrity.  
After generating a forwarding ticket, nodes \(N_{S}\) and \(N_{1}\) will keep a copy separately as the forwarding proof. When node \(N_{1}\) encounters another node \(N_{2}\) with smaller delivery delay, they will insert their node identifiers and encounter time to the forwarding path, and sign the information by the secret key, to generate a new forwarding ticket. Other forwarding nodes will continue the same operation until encountering the destination node. We can see that any node cannot modify the forwarding path and deny the forwarding behavior, because of their digital signatures. So TTP must be able to find the message's last forwarding node by forwarding ticket.  
Although TTP can find the last forwarding node, it cannot know whether the message has been dropped deliberately or due to TTL expiring. In order to check whether a message has been dropped deliberately, TTP needs the contact records between the forwarding nodes and destination node. In the CBCAIS scheme, when two nodes \(N_{i}\) and \(N_{j}\) meet, they will generate an encounter ticket, as shown in Figure 5.  
In the encounter ticket, \(N_{i}\), \(N_{j}\) are node identifiers; \(t^{1}_{N_{i}-N_{j}}\)... \(t^{n}_{N_{i}-N_{j}}\) are the times when nodes \(N_{i}\) and \(N_{j}\) encounter; \(Time^{1}_{N_{i}-N_{j}}\)... \(Time^{n}_{N_{i}-N_{j}}\) are inter-contact time samples between nodes \(N_{i}\) and \(N_{j}\) as in Equation (1); \(Sig_{Ni}\), \(Sig_{Ni}\) are digital signatures of nodes \(N_{i}\) and \(N_{j}\), respectively; \(EK_{Ni}\) is the private key of node \(N_{i}\); and \(H\) is the hash function to generate a summary to ensure the integrity of the message.  
Combining the forwarding ticket and the encounter ticket, TTP can check if the message has been dropped deliberately by a forwarding node. As shown in Figure 6, we can know the message receiving time \(t_{mc}\), TTL, and the last encounter time \(t^{n}_{N_{i}-N_{D}}\) between forwarding node \(N_{i}\) and destination node \(N_{D}\) from the forwarding ticket and the encounter ticket, respectively. If a forwarding node drops the message at time \(t_{drop}\) before \(t^{n}_{N_{i}-N_{D}}\), the misbehavior must be found by TTP, because the destination node cannot accept the message at time \(t^{n}_{N_{i}-N_{D}}\). The misbehavior node will be docked some credits to compensate for the loss of other nodes. In CBCAIS, we assume that the misbehavior node is punished by the removal of lots of credits, so any rational node will not discard messages deliberately.