DTN(Delay Tolerant Networks)是一種缺乏網路基礎設備的網路架構，在這類的網路架構下，無線節點之間的通訊連線並非同時存在，而是間歇式建立的。因為節點的移動、或是裝置省電模式運作與環境因素的影響，造成連線可能不定時的失效。有不保證連線特性的網路，在DTN網路中節點間相遇的機會很少，節點間利用 Store-Carry-Forward 的方式傳遞訊息，且有相當長的傳遞延遲(Propagation Delay)。在這樣的網路特性下，傳統的文獻中，都是假設所有節點都會幫忙傳遞。但不幸的，在現實生活中有自私節點(Selfish Nodes)的存在，因自己本身設備資源有限，如電力資源、網路資源...等，節點不願意幫忙傳送訊息，這些自私節點的存在，會對DTN網路架構造成破壞，導致無法傳送訊息到目的地。為了解決自私節點的問題，我們提出了MTBIS(Mobile Trusted Bank of Incentive Strategies)，當發送節點(Source Node)要求傳送訊息時，給予回饋給幫忙轉傳訊息的節點，來鼓勵節點間互相幫忙傳送訊息，我們稱這些回饋為Incentive Credit。而節點也可利用Incentive Credit來要求別的節點幫忙轉傳訊息。另外也加入SI(Social Incentive)機制，與DGT(Dynamic Grudger Threshold) ，吸引自私節點願意幫忙轉傳訊息，改進了 MTBIS 在自私節點環境下的不足， 利用經濟學的角度來解決節點運用Credit的問題，借此提高訊息的傳遞率(Delivery Ratio)。 本篇研究也注重於自私節點的模擬，利用四種不同特性的節點： Sucker(傻瓜)、Cheater (騙子)、Grudger(小氣鬼)、Ecci(投機者)， 這些自私節點會照成DTN在設計上無法使用，甚至降低訊息的傳達率，因此我們模擬了這些自私節點的行為，並且使用我們所提出的獎勵機制，來解決這些自私節點的問題，實驗結果也證明，Grudger可以有效的抑制自私節點對效能大幅降低的問題，與傳統的演算法相較，效能高出34%。 / DTN (Delay Tolerant Networks) is a network structure without need to use any infrastructure. In DTNs, wireless connections between nodes do not always exist, i.e., nodes are connected intermittently. Due to the mobility, power issues, or surrounding environment of nodes, connections between nodes may be disruptive occasionally or randomly. In a DTN, nodes usually transfer the message to the encountering nodes. By this way, the messages are stored, carried, and forwarded to the next nodes, possibly the destination. However, in reality, nodes may not be willing to help each other for the message forwarding. More specifically, there are “Selfish nodes” which refuse to forward messages due to issues such as energy and network bandwidth. Thus it will prevent messages from being forwarded to its destination. In order to solve the problem of message forwarding failure caused by selfish nodes, we proposed an Incentive Strategy called “MTBIS (Mobile Trusted Bank and Incentive Strategies)”. We construct a rewarding scheme called “Incentive Credit” for nodes who forward the messages for the source node. In addition, to increase the intention of the selfish nodes for forwarding messages, we add two more mechanism called SI(Social Incentive) and DGT(Dynamic Grudger Threshold). The DGT uses credits to solve selfish node problems from an economics point of view to enhance MTBIS to work with existence of selfish nodes. In this thesis, we emphasis on the simulation of the behaviors of selfish nodes, using four different types of nodes: the “Sucker”, the “Cheater”, the “Grudger”, and the “Ecci”. These selfish nodes will decrease the success rate of message forwarding, and even make the DTN unusable. We simulated the behaviors of these selfish nodes, using the rewarding scheme we proposed. From the results of our experiment, we see that the Grudger can effectively deal with performance issues caused by selfish nodes, and the system can gain 34% in performance compared to the traditional algorithms.

耐延遲網路(Delay Tolerant Networks)上的路由協定可以區分為兩大類:flooding-based protocols 跟forwarding-based protocols。網路編碼(Network Coding)是一種編碼技術可以提高訊息傳輸的可靠度；並且運作時不需要知道整體網路的拓樸資訊。 我們提出的演算法結合了flooding-based protocols 跟forwarding-based protocol特性，最主要的概念是讓訊息不是被傳送給每一個節點，而是傳送給朝向目的地或是接近目的地的節點。當節點相遇時，我們的方法會利用節點的路徑、移動方向與速度去預測到達目的地的機率。同時我們利用網路編碼的技巧傳送編碼後的資料來代替訊息的片段，來避免重複傳送多餘的訊息；並讓通訊更加可靠。根據實驗模擬的結果，我們的機制有較好的效能，特別是在頻寬的使用上。 / The routing protocols of delay tolerant networks could be divided in two categories: flooding-based protocols and forwarding-based protocols. Network coding is an encoding technique that could make data transmission more reliable. It operates without the needed of information about the network topology. We proposed a routing protocol integrating the characteristic of flooding-based protocol and forwarding-based protocol. The main idea of our protocol is to let message would not be flooded to every node but to the nodes moving toward or moving closer to destination. When nodes contact with each other, our approach will use the path of node, node’s moving direction and its velocity to estimate the probability to reach the destination of message. At the same time, we exploit network coding to transmit coded block instead of message fragment in order to avoid sending redundant replication, make data transmit more reliable and more robust to packet losses or delays. From the result of simulation, we could see that our protocol have a higher performance especially in the bandwidth consumption compared to other protocols.

在DTN(Delay Tolerant Networks)這類的網路架構下，無線節點之 間的通訊連線是採非連續性建立的。DTN 路由協定中, 決定中繼節點 方式大致可以分成兩類:依地理位置考量的路由協定（Geographic Routing Protocal）和依社交模式考量的路由協定（Social-based Routing Portocal）。 由於人與人間的互動是透過社交關係, 但是真實的資訊傳遞又須 仰賴當時的地理位置。因此我們提出的演算法將網路拓墣分成社交層與地理層, 在社交層中利用Social Ally Selection Algorithm 挑選出合適的社交盟友(Social Ally)。在地理層中利用Geographic Messenger Forwarding Algorithm 挑選合適的節點將訊息傳送給朝向目的地或是社交中繼站的節點。根據實驗模擬結果, 我們的路由協定能有較佳的傳遞成功率, 並降低了延遲時間。 / Delay Tolerant networks (DTN) may lack continuous network connectivity. Most of these DTN routing protocol, which attempt to make better routing decision, could be divided in two categories: Geographic routing protocols and Social-based routing protocols. Due to the interaction between people through social behaviors and message transmissions rely on geographic position information, we proposed a routing protocol which network topology is divided into two sub layers: social layer and geographic layer. In social layer, we propose a Social Ally Selection Algorithm to decide social allies that are controlled to improve delivery performance. In geographic layer, we propose a Geographic Messenger Forwarding Algorithm to transmit message to the nodes moving toward to social ally or destination. According to the simulation results, we could show that our routing protocol have higher delivery ratio and lower delay latency compare to other protocols.

在傳統的DTN路由協定中，由於網路拓樸的快速變動，為了能將訊息封包傳送到目的地，通常是透過大量的複製，或是透過資訊的過濾與計算，將封包交由適合的節點來協助傳送。 然而在電池電源有限的條件之下，過於冗餘的封包複製傳遞，或CPU運算的大量使用，將使得節點容易因電量耗盡而失去傳遞的功能，不只是造成整體系統的存活時間(System Lifetime)降低，亦非常不利於維持整體網路的傳遞成功率(Delivery Ratio)。 在旅行的過程中，同行的人們通常具有相同的移動軌跡以及最終目的地，因而形成團體行動的模式；針對這樣的特性，我們採用每個團隊只留下一位領隊來統籌探索鄰居及封包傳遞的概念，透過GPS的資訊輔助來設計出組隊省電機制，延長節點存活時間，進而提升系統存活時間，並在運算複雜度較低且封包冗餘複製亦降低的狀況下，仍保有不錯的傳遞成功率以及較低的效能衰減。 / In traditional routing protocols of DTNs, most of them are using redundancy messages and information computing to make a good relay decision. Due to energy limitation, too many redundant message transmissions or high computing will make nodes die off quickly. It will decrease the system lifetime and diminish the delivery ratio of the whole system. When people go on a tour, friends always form a group due that members have a similar moving path and destination. Based on the features of moving patterns, we design a grouping scheme, namely, Energy-aware Grouping, with the concept that there is only one node awake in a group in charge of contact and message transmissions. With the assistance by GPS, our method has reduced the numbers of redundant message transmissions and information computing. Simulation results show that it can extend the system lifetime with maintaining still good delivery ratio

在耐延遲網路(Delay Tolerant Network)中，因節點之間的高移動性、連接的不確定性環境嚴苛限制，採用Store-And-Forward 訊息傳輸的模式提供一個可接受的網路表現。常見的路由協定可分為機會路由、基於預測的路由以及調度路由，然而這些路由協定使用在市區環境中，有些許不足的地方，因此我們提出適用在市區封包轉發策略。 我們提出的以公車亭為基礎之耐延遲車載網路封包轉發策略，是在市區環境中建立一個以公車亭為基礎的資料傳送架構，包含汽車、公車、公車站、公車轉運站四種節點。我們建立節點與節點相遇時資料傳送規則，例如汽車與汽車相遇、汽車與公車相遇、公車與公車站相遇、公車與公車轉運站相遇、公車轉運站與公車相遇、公車站與汽車相遇、汽車與目的地相遇時各自有不同的資料傳送判斷與限制。 實驗結果也證明所提出的演算法，除了可以有效地減少延遲傳送時間並提高訊息成功傳送率，及在各節點有限的緩衝區大小下，我們的封包轉發策略有著最突出的效能。 / In Delay Tolerant Networks (DTNs), there does not exist an end-to-end path due to intermittent connectivity and high node mobility. Messages are stored for a period of time at network nodes and are conveyed hop-by-hop to the destination. The current DTN routing protocols can be summarized into three categories: opportunistic, prediction-based and scheduling protocols. However, these routing protocols have some deficiencies and are not specifically focused on the urban areas. Based on the characteristics of urban areas, we proposed a kiosk based packet forwarding strategy for vehicular delay tolerant networks. We established the rules of data transmission when one node contacts other nodes. More specifically, Car-to-Car, Car-to-Bus, Bus-to-Bus stop, Bus-to-Bus transfer station, Bus transfer station-to-Bus, Bus stop-to-Car ,Car-to-Destination contacts, have different judgments and restrictions for data forwarding. The simulation results demonstrate that we proposed packet forwarding strategy would reduce the delivery delay, and improve the successful delivery rate. Especially with limited buffer and little overhead, our proposed strategy has the most prominent performance.

在耐延遲網路環境下節點的相遇情況不是很頻繁，這可能導致節點間的連線斷斷續續，使得有效地將訊息傳遞成為一件困難的事情。藉由社群感知轉送機制的中間度指標特性，可以來提升傳送成功率。雖然大多數研究幾乎都是將訊息轉送到單一目的地或是多個且已知的目的地。然而，一些應用像是廣告的散佈，要將訊息送給對訊息有興趣的人，但卻不知道是誰。因此，關鍵的問題為如何建立社群網路關係的親密度機制，來選擇作為轉送訊息的節點，並利用群體廣播的方式盡可能有效地傳播至最多可能目標目的地，進而提升效能。 本論文以群播機制和社群感知當作基礎概念，來設計新的轉送訊息的方法和公式化選擇中繼節點的機制。最後，我們使用政治大學實際軌跡來模擬，將模擬結果與其它路由演算法比較，其結果證明我們所提出的方法能提高訊息傳送成功率和正確率，降低傳送延遲時間和傳送訊息的成本。 / In delay tolerant networks (DTNs), nodes infrequently encounter with each others. This results in intermittent connectivity of the nodes, and makes it difficult to deliver the message effectively. A social-aware forwarding scheme can help for successful delivery ratio by utilizing the characteristic of their centrality metric. Most of the previous studies focus on message delivery to single destination or some priori known destinations. However, some applications like advertisement dissemination may not know who will be the interested persons to be delivered. Therefore, the key challenge is how to establish the social relationship strategy to select appropriate nodes as relays, and furthermore to use multicasting to disseminate effectively as many “target” destinations as possible to improve the performance. This thesis developed a new strategy which has a new forwarding message scheme and formulates the selection of the relay nodes based on the concept of the multicasting and the social network. Finally, we used the reality trace data of National Chengchi University to simulate. The simulation results are compared to others DTNs routing protocols as well as other social-aware forwarding schemes. The results showed that our proposed approach can enhance the successful delivery ratio and delivery accuracy, decrease the delivery delay and reduce the delivery overhead.

在耐延遲網路中，沒有網路服務的使用者，可以藉由各節點間的短距離傳送，透過一個間斷性的連結將資料傳送至目的地。因此，在本研究，當使用者在校園環境中，欲將手邊的資料傳送給其他使用者，但無法連結上網際網路時，可以透過與目標節點關聯性較高的節點幫忙以達到傳送資料之目的。 本論文提出一基於個人與社群資訊的資料傳送方法，以個人興趣、個人資訊與朋友關係等三個面向去分析適合用來幫助傳送資料的節點。在每個訊息中，我們加入一級別值，並在相遇到其他節點時做資訊的交換與計算，並利用選擇較高級別值的節點轉送，使資料可以透過較有效率的路線傳送至目的地。最後，我們將本論文方法與其它資料傳送方法比較評估效能，模擬結果顯示我們提出的傳送方法有較優的傳送成功率與較低的資源耗費。 / In Delay Tolerant Networks (DTNs), the user without network service can, through short transmission between nodes, use an intermittent route to deliver messages to the destination. In our study, when a user in the campus environment wants to send its data to others but can’t link to Internet in that moment, the user can use the node which has higher relation degree with the destination to help forward the data. In this thesis, we proposed a social-based routing approach. It is based on aspects of personal interest, personal information, and social relation to analyze which node is appropriate for data relaying. For each data, a rank value is associated with it. When the node encounters with other nodes, it will exchange and calculate data information to renew the rank value. Based on the rank value, data can be relayed to nodes with higher rank values, and thus to the destination through a more efficient way. Finally, we evaluated our approach, and compared with other routing schemes. The simulation results showed that our proposed approach had better delivery probability and lower resource cost.

許多國家正面臨因嚴重的交通壅塞所帶來龐大的經濟損失，同樣在台灣也面臨相同問題，根本解決之道就是找出壅塞路段，並即時地告知車輛駕駛以迴避此路段。因此如何有效率地偵測出壅塞路段，是當前重要的議題。以往大多透過長期所累積的統計數據，針對各路段收集行駛於該路段所有車輛的平均速度，來獲得該路段的交通狀況，但卻無法立即反應即時路況。 因此我們提出以耐延遲車載網路方式，收集路況資訊與彙整旅途時程，透過具有全球定位系統(GPS)以及無線網路的車輛來進行路況交通資訊的收整與交換。再透過本研究所提出路況交通覺知路由協定(RTARP)，以One-Hop Controlled Flooding的傳輸方式在節點與節點相遇時進行路況資訊的傳送，進而交換節點彼此間各自所存放各路段的路況資訊。 模擬實驗結果證明我們所提出的路由協定在路況交通資訊交換中，有效地減少網路傳輸負載、提高訊息送達成功率以及路況交通資訊(RTI)正確率。 / Many countries are concerning about the huge economic losses caused by the critical traffic congestion. We have the same problem in Taiwan. The solutions lie in finding the road section with traffic congestion first and informing drivers to avoid that section. But how to detect the road section with traffic congestion effectively is the most important issue of this research. Conventionally, the real-time road traffic is mostly predicted by long-term accumulated statistics calculated by the collection of the average speed of cars on the same road section. But this way can’t provide the real-time road traffic immediately. Based on vehicles with GPS and the capability of WiFi, we proposed gathering road traffic information and consolidating travel time estimation using vehicular delay tolerant networks. We also proposed the Road Traffic Awareness Routing Protocol (RTARP) to exchange the road traffic information preserved individually by One-Hop Controlled Flooding during nodes’ encounter. The results of simulations prove the routing protocol we proposed can effectively reduce the transmission overhead, improve the delivery ratio and the accuracy of the road traffic information.

在耐延遲網路上，離線的使用者，可以透過節點的相遇，以點對點之特定訊息繞送方法，將資訊傳遞至目的地。如此解決了使用者暫時無法上網時欲傳遞資訊之困難。因此，在本研究中，當使用者在某一地區，欲查詢該地區相關之資訊，但又一時無法連上網際網路時，則可透過耐延遲網路之特性，尋求其它同樣使用本服務之使用者幫忙以達到查詢之目的。 本論文提出一適地性服務之資料搜尋方法，以三層式區域概念，及混合式節點型態，並透過資料訊息複製、查詢訊息複製、資料回覆及資料同步等四項策略來達成使用者查詢之目的。特別在訊息傳遞方面，提出一訊息佇列選擇演算法，賦予優先權概念於每一訊息中，使得較為重要之訊息得以優先傳送，藉此提高查詢之成功率及減少查詢之延遲時間。最後，我們將本論文方法與其它查詢方法比較評估效能，其模擬結果顯示我們提出的方法有較優的查詢效率與延遲。 / In Delay Tolerant Networks (DTNs), the offline users can, through the encountering nodes, use the specific peer-to-peer message routing approach to deliver messages to the destination. Thus, it solves the problem that users have the demands to deliver messages while they are temporarily not able to connect to Internet. Therefore, by the characteristics of DTNs, people who are not online can still query some location based information, with the help of users using the same service in the nearby area. In this thesis, we proposed a Location-based content search approach. Based on the concept of three-tier area and hybrid node types, we presented four strategies to solve the query problem. They are Data Replication, Query Replication, Data Reply and Data synchronization strategies. Especially in message transferring, we proposed a Message Queue Selection algorithm. We set the priority concept to every message such that the most important one could be sent first. In this way, it can increase the query success ratio and reduce the query delay time. Finally, we evaluated our approach, and compared with other routing schemes. The simulation results showed that our proposed approach had better query efficiency and shorter delay.

在耐延遲網路(Delay Tolerant Network)中，因為節點具有移動性，因此找不到穩定且持續的點對點資料傳送路徑。常見的路由協定可分為機會路由、基於預測的路由以及調度路由，然而這些路由協定使用在市區環境中，有著些許不足與不適用，因此本論文提出一個適用在市區資料傳送的演算法。 本論文提出之混合階層式路由演算法，是在市區環境中建立一個以公車為基礎的資料傳送架構，包含行人與公車兩種節點。我們建立節點與節點相遇時資料交換傳送規則，例如行人與行人相遇、行人與公車相遇或是公車與公車相遇時各自有不同的資料傳送判斷與限制。 實驗結果也證明所提出之混合階層式演算法，除了可以有效地減少傳送延遲時間並提高訊息傳送成功率，並且在給定節點一定的移動速度與緩衝區大小下，我們的演算法有著最突出的效能。 / In Delay Tolerant Networks (DTNs), there is no guarantee that a stable connected path between source and destination nodes always exists because of high node mobility. The current DTN routing protocols can be summarized into three categories: opportunistic, prediction-based and scheduling protocols. However, these routing protocols have some deficiencies and are not specifically focused on the urban areas which have primarily two hierarchical nodes, namely pedestrian and bus nodes. We proposed a Hybrid Hierarchy Routing Protocol, a bus-based architecture for urban areas. We established the rules of data transmission when one node contacts other nodes. More specifically, Ped-to-Ped, Ped-to-Bus and Bus-to-Bus contacts, have different judgments and restrictions for data forwarding. The simulation results demonstrate that the Hybrid Hierarchy Routing Protocol can effectively reduce the delivery delay and improve the successful delivery rate. And in given certain speed and buffer sizes, our algorithm has the most prominent performance.