由於隨意網路(ad-hoc network)發展已久，促使人們發展許多新方法試圖增強網路的效能。近年來群集智慧(swarm intelligent)越來越熱門，許多研究透過模仿生物行為來解決網路上的路由問題。在一些研究中，提出透過分群策略將網路分成許多群集，在相同群集內的節點都可以與群集中的群集頭(cluster-head)相連接，並藉由cluster-head之間的連接，使封包在不同群集間傳遞，找到一條到達目的節點的路徑。此外，分群策略也可以延伸建構成弱連結支配集(Weakly Connected Dominating Sets，WCDS)。藉由這些技術，有研究提出以弱連結支配集為輔之基於蟻群需求式分群路由演算法(Weakly Connected Dominating Set Assisted Ant-based On-demand Clustering Routing Protocol)，根據前行的螞蟻封包(Forward_Ant)獲得網路上的資訊狀態並更新費洛蒙，且只會由WCDS成員廣播Forward_Ant給鄰近的WCDS成員，接著回退的螞蟻封包(Backward_Ant)會透過偽隨機比例選擇 (pseudo-random-proportional-selection)策略建構出來源節點到目的節點的較佳路徑。在本篇論文中，我們也依循分群策略，並調整支配集的數量形成支配集(Dominating Sets，DS)及強連接支配集(Connected Dominating Sets，CDS)，同時為了提升網路效能，我們提出了能量及hop感知的蟻群需求式分群路由演算法。最後將會以網路模擬器(Network Simulator version 2，NS-2)模擬，分別比較以DS、WCDS、CDS輔助能量及hop感知的蟻群需求式分群路由演算法的差異。

Ad hoc networks have been developed for quite a long time. Some approaches have been proposed to increase network efficiency. One of the popular approaches is based on swarm intelligent, which imitates the behavior of biological species to solve the network routing problem. Some recent study builds clusters in a network by a clustering scheme. The node which is in a cluster can be associated with a cluster-head which is in the same cluster. By the connection between the cluster-heads, we can find a routing path to the destination node. Meanwhile, the weakly connected dominating sets (WCDS) can be formed by a clustering scheme. By the techniques, Weakly Connected Dominating Set Assisted Ant-based On-demand Clustering Routing Protocol has been proposed. The Forward_Ant is only broadcast by the WCDS member. The pheromone value can be updated by the Forward_Ant. The Backward_Ant then chooses a routing path by pseudo-random-proportional-selection scheme. In this study, we use dominating sets (DS) and connected dominating sets (CDS) which are derived from the clustering scheme to adjust the dominating set. Moreover, we propose a residual energy-over-hop based ant colony on-demand clustering routing protocol to find the routing path. Comprehensive experiments show that the proposed scheme can increase the network efficiency. Simulation show the difference that ant-based on-demand routing protocol is assisted by DS, WCDS, CDS.

[1] Jianping Wang, Eseosa Osagie, Parimala Thulasiraman, Ruppa K. Thulasiram, HOPNET: A hybrid ant colony optimization routing algorithm for mobile ad hoc network, Ad Hoc Networks, 2009, 690-705
[2] Perkins CE, Bhagwat P. Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers. SIGCOMM Comput Commun Rev1994;24:234–44.
[3] Perkins CE, Royer EM. Ad-hoc on-demand distance vector routing. Mobile computing systems and applications, 1999. In: Proceedings. WMCSA ‘99.Second IEEE workshop on, New Orleans, LA, USA; 1999. p. 90–100.
[4] Pearlman MR, Haas ZJ. Determining the optimal configuration for the zone routing protocol. Selected Areas in Communications, IEEE Journal on 1999;17:1395–414.
[5] Yu JY, Chong PHJ. A survey of clustering schemes for mobile ad hoc networks. Communications Surveys & Tutorials, IEEE. vol. 7. First Qtr; 2005. p. 32–48.
[6] Gianni Di Caro, Frederick Ducatelle and Luca Maria Gambardella,Swarm Intelligence for routing in mobile ad hoc networks, Proceedings 2005 IEEE Swarm Intelligence Symposium, 2005, 76 - 83
[7] Camilo T, Carreto C, Silva JS, Boavida F. An energy-efficient ant-based routing algorithm for wireless sensor networks. In: Proceedings of ANTS 2006 –the 5th international workshop on ant colony optimization and swarm intelligence. vol. 4150; 2006. p. 49–59.
[8] Marco Dorigo, Mauro Birattari, Thomas Stutzle, Ant colony optimization, IEEE Computational Intelligence Magazine, 2006, 28 - 39
[9] Kuen-Han Li, Jenq-Shiou Leu, Jíri Hoek, Ant-Based On-Demand Clustering Routing Protocol for Mobile Ad-Hoc Networks, Computers and Electrical Engineering, Elsevier,2015, 62–76
[10] Jenq-Shiou Leu, Wei-Hsiang Lin, Jheng-Huei Chen, P2P resource searching with Cloning Random Walker assisted by Weakly Connected Dominating Set, The Journal of Supercomputing, 2014, 443–458
[11] B. Han, W. Jia, Clustering wireless ad hoc networks with weakly connected dominating set, Journal of Parallel and Distributed Computing, 2007, 727-737
[12] Alessandro Meit,Alessandro Panconesi,Jaikumar Radhakrishnan,Aravind Srinivasan, Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons, Journal of Computer and System Sciences, 2005, 467-479
[13] Shuang B, Li Z, Chen J, An Ant-Based On-Demand Energy Route Protocol for IEEE 802.15.4 Mesh Network, International Journal of Wireless Information Networks, 2009, 225-236
[14] M. K. Marina, S. R. Das, On-demand multipath distance vector routing in ad hoc networks, Network Protocols, 2001. Ninth International Conference on, 2001, 14 - 23
[15] Jheng-Huei Chen, Jenq-Shiou Leu, Kuen-Han, Hybrid searching scheme supported by dynamic weighted distributed label clustering in social networks, 2013 19th Asia-Pacific Conference on Communications (APCC), 2013, 609 - 613