在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

Les réseaux de capteurs sans fils (RCSFs) suscitent un intérêt croissant depuis une vingtaine d'années. La première partie de cette thèse est consacré à l'étude de l'efficacité de compression de données corrélées provenant d'un RCSF et acheminées vers un point de collecte à l'aide du codage réseau linéaire aléatoire. Les conditions nécessaires et suffisantes sont obtenues pour récupérer parfaitement les données que les capteurs mesurent. Puis on considère les nœuds dans un RCSF collaborant afin d'exécuter une tâche donnée (acquisition, détection...), pour laquelle chaque nœud a potentiellement un niveau d'expertise différent. La seconde partie de cette thèse est dédiée à la conception et à l'analyse d'algorithmes d'auto-évaluation distribués (AED), qui permettent à chaque nœud d'auto-évaluer son niveau d’expert. Trois types de problèmes sont considérés: i) la détection distribuée des nœuds défaillants (DDD), qui permet d'identifier les nœuds équipés de capteurs défectueux dans un RCSF; ii) la DDD dans un réseau tolérant aux déconnections (RTD) dont la topologie est dynamique et le degré de connectivité très faible; iii) la AED avec interactions pair à pair. Les résultats théoriques sont utiles pour configurer les paramètres des algorithmes. / Wireless sensor networks (WSNs) have attracted much interests in the last decade. The first part of this thesis considers sparse random linear network coding is for data gathering and compression in WSNs. An information-theoretic approach is applied to demonstrate the necessary and sufficient conditions to realize the asymptotically perfect reconstruction under MAP estimation. The second part of the thesis concerns the distributed self-rating (DSR) problem, for WSNs with nodes that have different ability of performing some task (sensing, detection...). The main assumption is that each node does not know and needs to estimate its ability. Depending on the number of ability levels and the communication conditions, three sub-problems have been addressed: i) distributed faulty node detection (DFD) to identify the nodes equipped with defective sensors in dense WSNs; ii) DFD in delay tolerant networks (DTNs) with sparse and intermittent connectivity; iii) DSR using pairwise comparison. Distributed algorithms have been proposed and analyzed. Theoretical results assess the effectiveness of the proposed solution and give guidelines in the design of the algorithm.

A Disruption Tolerant Network (DTN) is a sparse network where connectivity is regulated by the proximity of mobile nodes. Connections are sporadic and the delivery rate is closely related to node movement. As network resources often are limited in such settings, it is useful to monitor the network in order to make more efficient communication decisions. This study investigates existing routing protocols and monitoring tools for DTN that best cope with the requirements of a tactical military network. A model is proposed to estimate source to destination delay in DTN. This model is evaluated in a Java-based software simulator called The ONE. In order to match the tactical military environment, two scenarios are constructed. The squad scenario simulates the formation movement pattern of several squads and the hierarchical communication scheme that is maintained in a military context. The other scenario simulates a convoy line movement of a military group during transportation. The results of this study show that the proposed mechanism can improve delivery rate and reduce network overhead in settings with strict buffer limitations. The estimation worked best in scenarios that contained some patterns of movement or communication. These patterns are resembled in the model's collected data and the model can provide the user with rough estimates of end-to-end delays in the network. Primary use of this model has been to reduce number of old messages in the network, but other applications like anomaly detection are also discussed in this work. / Ett avbrottstolerant nätverk (DTN) är ett glest nät där konnektiviteten avgörs av närheten bland de rörliga noderna i nätverket. Avbrotten i ett sådant nät förekommer ofta och sporadiskt. Eftersom nätverksresurserna oftast är begränsade i sådana sammanhang, så är det lämpligt att övervaka nätverket för att göra det möjligt att fatta mer effektiva kommunikationsbeslut. Det här arbetet undersöker olika routingalgoritmer och övervakningsvektyg för DTN med hänsyn till de krav som ställs av ett taktiskt nät. En modell för att uppskatta fördröjningen från källa till destination är framtagen i arbetet. Modellen är utvärderad med hjälp av en Javabaserad mjukvarusimulator som heter The ONE. För att bäst representera den miljö som uppstår i militära sammanhang är två scenarion framtagna. Det första är ett truppscenario där nodernar rör sig i fromationer och nättrafiken följer den hierarkiska modellen som används i militär kommunikation. Det andra scenariot är ett konvojscenario där enheter marcherar på led. Resultaten från denna studie visar att den föreslagna modellen kan öka andelen levererade meddelanden och minska nätverksbelastningen i en miljö där bufferstorleken hos noderna är begränsad. Uppskattningen visade sig fungera bäst i scenarion som innehöll någon form av mönster bland nodernas rörelse eller deras kommunikation. Dessa mönster återspeglas i modellens insamlade data och modellen kan förse användaren med en grov estimering av slutfördröjningen till alla destinationer i nätet. Modellen har i huvudsak använts till att minska antalet gamla meddelanden i nätet, men arbetet berör även andra användningsområden som anomalidetektion.

在耐延遲網路(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.

No description available.