蟻群傳染目標的最佳化--一種移動Ad-hoc網路服務探索演算法

Abstract

基於已被提出之各種不同服務探索協定的特徵，本研究專注於探討資源與服務探索協定的發展，利用網路中各個節點的數據型態，創造和主體相關的模塊。蟻群優化算法和傳染病傳播概念的優化被應用到整個網路訊息的擴散中，並在網路中開始請求搜尋的節點、與提供服務的節點之間，創造溝通橋樑。 本文中使用的方法包括對不同產品的研究、依設計功能來做的分類、這些應用程式對應 MANET 網路的特點並且通過資源發展和服務探索協定來驗證其對事件發生的功能和適當的反應，由於網路動態的特性和選擇一個適當網路的仿真工具去複制和測試協議中的預期結果，顯示出它的優點和不足處。通過各種不同圖形的比較和相對應的描述來展現資源和服務探索協定的效率和優越表現。通過對沒有數據類型的創造或者本體論分類和訊息使用數量的相比，在協議傳播階段，消息傳播數量得到有效的降低。在網路中測試衝擊效應展示出了協議的高可靠性和在衝擊隨時可能增加爆發時，在網路中服務發現的數量產生永恆不變的結果。其他結果包括在協議中系統過載導致的無效搜索影響，搜索訊息的數量和在兼容匹配時間的影響。 在本文中發展出的資源和服務探索協定，不僅達到了 MANET 網路的特性和需求，同時通過模擬得到的結果顯示在先進工藝開發過程中 MANET 網路的多功能性、運用性、與其在更先進程序中----例如利用網路中各個不同的設備來完成的自動服務組合----的先進性。

Nodes participating in mobile ad-hoc networks have the liberty to join, leave and move across it, inducing the constant change in the topology and presenting a challenge for the composition and maintenance of the communication via between nodes. Considering the characteristics of different service discovery protocols proposed in the past years, the present work explores the development of a resource and service discovery protocol that makes use of the data type each node in the network handles, to create blocks related among them through an ontology. Concepts of ant colony optimization algorithms and infectious spread are applied to optimize the diffusion of message across the network, as well as to create the communication links between nodes starting search requests and nodes offering services in the network. The methods used in the thesis include the study of different works as well as the classification of the same according to its design features, the application of these solutions to fit the characteristics of MANET networks, the development of the proposed resource and service discovery protocol validating its functionalities and proper response to the events occurring due to the dynamic nature of the network and the selection of an appropriate network simulation tool to reproduce and test the expected outcomes of the proposed protocol showing the advantages and limitations of the same. The efficiency and satisfactory performance of the proposed resource and service discovery protocol is presented in the different graphical comparisons and described in the corresponding subsections of the same. A significant decrease of the number of transmitted messages during the dissemination phase of the proposed protocol is found as compared to the amount of messages used when no data type relation is created or classified through an ontology. The results obtained when testing for the miss hit effect in the network show the high level of reliability of the protocol, producing constant outcomes of the number of services discovered in the network when the ratio of invalid services populating the network increases. Other results include the invalid search effect on system overload induced by the protocol, amount of search messages and effect on compatibility match process time. The resource and service discovery protocol developed and fully implemented throughout the present thesis not only attains to the requirements and characteristics of MANET networks, but the results obtained through the simulations show the capability, functionality and advantages of its application in the development of more advanced processes such as automatic service composition making use of data type handled by different devices in a network.