| 摘要: | 在耐延遲網路(Delay Tolerant Networks, DTNs)中，由於節點移動的不可預期性造成的間斷式連線，網路中一個訊息的來源端到目的端難以建立一條end-to-end path來傳輸此訊息。因此，耐延遲網路採用了集束協定(Bundle Protocol)所提出的store-carry-and-forward方式取代傳統網路的store-and-forward方式來傳輸訊息。而一個來自於上層的訊息(Message)會在集束層(Bundle Layer)被切割成多個較小的資料單位，這些資料單位就叫做束(Bundle)。同時，為了確保束在網路中的傳輸可靠度，集束協定採用了保護傳輸機制(Custody Transfer)，透過其hop-by-hop的傳輸方式及重傳和確認回傳的機制來確保每個束在成功被網路中的下一個節點接收前不被丟棄。
然而使用集束協定可能會面臨兩個問題：透過保護傳輸機制，束的不可被丟棄性將會使網路中節點消耗許多儲存空間資源來儲存束，尤其是在資源有限的耐延遲網路中，這樣的情況可能會阻礙束在網路中的傳輸，進而降低了訊息抵達率；另外，由於耐延遲網路的間歇性連線的特性，要等到一個訊息的所有切割束都抵達訊息目的端並且完成一個訊息的回復是相對困難的。
因此，本篇論文提出了一個基於賽局理論的儲存空間管理機制(Buffer Management based on Game Theory, BMGT)，網路中節點可以透過此機制來管理其儲存空間的使用情況進而避免發生儲存空間不足的壅塞情形。當網路中的兩個節點相遇後，這兩個相遇節點即會進入轉送賽局(Forwarding game)，並且根據賽局理論模型同時考慮節點自身的儲存空間使用情況來決定是否要接收或是轉送束給其相遇節點。BMGT的目的就是希望透過賽局理論將節點儲存空間資源納入考量，對於網路中兩相遇節點決定出一個合適轉送或是接收機率。同時，為了避免儲存空間溢出(Buffer overflow)，我們提出了激勵函式(Incentive function)。激勵函式的概念是希望兩相遇節點中，擁有較低儲存空間使用率的節點有較高的機率會採取接收束的行為，而擁有較高儲存空間使用率的節點有較高的機率會採取轉送束的行為。如此一來不但可以避免儲存空間壅塞問題同時還能促進束在網路中的流動。另外，BMGT在訊息的產生上採用了湧泉編碼(Fountain Code)的原理，使得訊息的目的端只需要接收到部分的束即可回復其原始訊息。模擬結果顯示，BMGT不但可以達到較有效的儲存空間資源分配，同時解決集束協定的儲存空間壅塞問題，並且達到較好的網路效能。
;Delay tolerant networks (DTNs) contain resource-constrained nodes moving in highly dynamic network environments, which makes persistent end-to-end routing paths impossible between any pair of source and destination nodes. The DTN architecture with the Bundle Protocol (BP) are thus advocated a reliable message delivery service on intermittently connected networks. The BP provides a new encapsulation representation by which a message from an upper layer is divided into a series of bundles. Instead of store-and-forward paradigms commonly used in wireless and mobile ad hoc networks, the DTN architecture adopts the \textit{store-carry-and forward} paradigm by which nodes can store bundles, carry them and forward these bundles to next encountered nodes during movement in a network. In addition, BP guarantees delivery reliability among bundles using the \textit{Custody Transfer} mechanism. Nodes are not allowed to drop any bundles of which they take the custody until these bundles are successfully delivered to next nodes that can take the custody in turn.
Using the Bundle Protocol in DTNs, however, faces two possible problems. First, opportunistic or unpredictable contacts among nodes may make it difficult for all divided bundles to arrive at a destination, this problem which might enforce the failure of message reconstruction services in a network. Second, the non-dropped feature of custody transfer may cause nodes spend excessive storage space to store custody bundles, this problem which might induce buffer overflow on the nodes.
In this study, we propose a Buffer Management scheme based on Game Theory (BMGT) that nodes can control the number of bundles in their own storage and avoid the likelihood of bundle congestion in DTNs. Regarding the first problem above, BMGT combines the principle of Fountain Code that any destination does not need to receive all divided bundles to recover original message. Regarding the second problem, BMGT derives the appropriate forwarding and receiving probability based on the game theory model, which takes node storage utilization into account, for two nodes in communications. In BMGT, nodes will enter a forwarding game upon contacting with the other nodes and then follow the game theory model to select a forward or receiving action with some merit of reward. To prevent buffer overflow, an incentive function is further devised to encourage reciprocal actions of bundle forwarding and receiving between two nodes in contact. Finally, we conduct extensive simulation to investigate the effects of BMGT under various synthetic contexts. Performance results manifest that BMGT can not only achieve efficient storage resource allocation but also resolve the congestion issue against the convention of Bundle Protocol in DTNs. |
