DAGGraph: Blockchain Suitable for Mobile Ad Hoc Networks

doi:10.3778/j.issn.1673-9418.2211070

Abstract

Abstract: Aiming at the challenges faced by the combination of blockchain and mobile ad hoc networks, a system model DAGGraph based on DAG (directed acyclic graph) is proposed, which adopts the DAG structure to adapt to the network split caused by mobility. Firstly, the clustering algorithm is optimized, and an algorithm for limiting the density of nodes in the cluster is proposed, which effectively solves the problem of throughput reduction and energy consumption increase caused by the uncontrolled increase of the number of nodes in the cluster. Secondly, for network splitting and merging caused by the rapid movement of the nodes, a block recovery algorithm based on data synchronization between cluster heads is proposed. The legal blocks generated by all nodes are preserved through DAG. When the network is merged, the original cluster heads exchange their generated block branches, realizing the recovery of the block branches. Finally, a simplified block appending algorithm is proposed, which simplifies the block appending process on the premise that the internal nodes are trusted, reduces the error caused by block propagation in the mobile environment, shortens the block confirmation time, and improves the system throughput. Security analysis shows that DAGGraph can resist common attacks against blockchain, and resist denial-of-service attacks against mobile ad hoc networks. Simulation results show that the latency and throughput of DAGGraph are better than existing IoT blockchain solutions in most cases.

Key words: blockchain, mobile ad hoc networks, clustering algorithm, consensus mechanism

摘要： 针对区块链与移动自组网结合所面临的挑战，采用有向无环图（DAG）结构适配移动性引发的网络分裂，提出一种基于DAG的系统模型DAGGraph。首先，对分簇算法进行优化，提出了簇内节点密度数量限制算法，从而有效解决了簇内节点数量不受控增加带来的吞吐量减小和能耗增加问题；其次，针对移动自组网节点快速移动引起的网络拆分与合并问题，提出了基于簇首间数据同步的区块恢复算法，通过DAG结构保留所有节点产生的合法区块，在网络合并时由原簇首交换产生的区块分支，实现了对区块分支的同步和恢复；最后，提出了一种简化的区块上链算法，在内部节点可信的前提下简化了区块的上链流程，减小了移动环境下区块传播产生的误差，缩短了区块的确认时间，提高了系统吞吐量。安全性分析表明，系统可以抵御针对区块链的常见攻击，并可以抵御针对移动自组网的拒绝服务攻击。仿真实验结果表明，DAGGraph的时延和吞吐量性能在大部分情况下优于已有的物联网区块链解决方案。

关键词: 区块链, 移动自组网, 分簇算法, 共识机制

ZHANG Wentao, HUANG Jianhua, GU Bin, NING Yuhao, GONG Zaiwei. DAGGraph: Blockchain Suitable for Mobile Ad Hoc Networks[J]. Journal of Frontiers of Computer Science and Technology, 2024, 18(1): 252-264.

张文韬, 黄建华, 顾彬, 宁宇豪, 宫在为. DAGGraph: 适合移动自组网的区块链[J]. 计算机科学与探索, 2024, 18(1): 252-264.

References

[1] ISLAM S, BADSHA S, SENGUPTA S. A light-weight block-chain architecture for V2V knowledge sharing at vehicular edges[C]//Proceedings of the 2020 IEEE International Smart Cities Conference. Piscataway: IEEE, 2020: 1-8.
[2] ABISHU H N, SEID A M, YACOB Y H, et al. Consensus mechanism for blockchain-enabled vehicle-to-vehicle energy trading in the Internet of electric vehicles[J]. IEEE Transactions on Vehicular Technology, 2021, 71(1): 946-960.
[3] HASSIJA V, CHAMOLA V, GARG S, et al. A blockchain-based framework for lightweight data sharing and energy trading in V2G network[J]. IEEE Transactions on Vehicular Technology, 2020, 69(6): 5799-5812.
[4] LAUBE A, MARTIN S, AL A K. A solution to the split & merge problem for blockchain-based applications in ad hoc networks[C]//Proceedings of the 8th International Confe-rence on Performance Evaluation and Modeling in Wired and Wireless Networks, Paris, Nov 26-28, 2019. Piscataway: IEEE, 2019: 1-6.
[5] CORDOVA D, LAUBE A, PUJOLLE G. BlockGraph: a block-chain for mobile ad hoc networks[C]//Proceedings of the 4th Cyber Security in Networking Conference, Lausanne, Oct 21-23, 2020. Piscataway: IEEE, 2020: 1-8.
[6] MORALES D C, VELLOSO P B, LAUBE A, et al. C4M: a partition-robust consensus algorithm for block-graph in mesh network[C]//Proceedings of the 5th Cyber Security in Net-working Conference, Abu Dhabi, Oct 12-14, 2021. Piscata-way: IEEE, 2021: 82-89.
[7] EPHREMIDES A, WIESELTHIER J E, BAKER D J. A de-sign concept for reliable mobile radio networks with fre-quency hopping signaling[J]. Proceedings of the IEEE, 1987, 75(1): 56-73.
[8] 陈志军, 史杏荣. 一种适合移动自组网的分簇算法[J]. 计算机工程与应用, 2007, 43(29): 159-161.
CHEN Z J, SHI X R. A clustering algorithm suitable for mobile ad hoc network[J]. Computer Engineering and Application, 2007, 43(29): 159-161.
[9] 宋人杰, 邹振婉, 周欣欣. 基于节点移动特性的移动P2P网络分簇算法[J]. 东北电力大学学报, 2016, 36(1): 87-90.
SONG R J, ZOU Z W, ZHUO X X. Clustering algorithm of mobile P2P network based on node mobility characteristics[J]. Journal of Northeast Electric Power University, 2016, 36(1): 87-90.
[10] 陈宇, 张勇, 陈实. 大规模卫星集群网络自适应加权分簇算法[J]. 北京理工大学学报, 2021, 41(11): 1188-1192.
CHEN Y, ZHANG Y, CHEN S. Adaptive weighted clus-tering algorithm for large-scale satellite cluster networks[J]. Transactions of Beijing Institute of Technology, 2021, 41(11): 1188-1192.
[11] 吴振华, 胡鹏. VANET中一种优化路由开销算法研究[J]. 南昌航空大学学报(自然科学版), 2016, 30(2): 28-36.
WU Z H, HU P. Research on an optimization routing cost algorithm in VANET[J]. Journal of Nanchang Hangkong University (Natural Sciences), 2016, 30(2): 28-36.
[12] 崔朝阳, 孙甲琦, 徐松艳, 等. 适用于集群无人机的自组网安全分簇算法[J]. 山东大学学报(理学版), 2018, 53(7): 51-59.
CUI C Y, SUN J Q, XU S Y, et al. A secure clustering algo-rithm for ad hoc networks suitable for swarming UAVs[J]. Journal of Shandong University (Natural Science), 2018, 53(7): 51-59.
[13] SOMPOLINSKY Y, ZOHAR A. Secure high-rate transac-tion processing in bitcoin[C]//LNCS 8975: Proceedings of the 19th International Conference on Financial Cryptogra-phy and Data Security, San Juan, Jan 26-30, 2015. Cham: Springer, 2015: 507-527.
[14] LI C, LI P, ZHUO D, et al. Scaling Nakamoto consensus to thousands of transactions per second[J]. arXiv:1805.03870, 2018.
[15] LEWENBERG Y, SOMPOLINSKY Y, ZOHAR A. Inclusive block chain protocols[C]//LNCS 8975: Proceedings of the 19th International Conference on Financial Cryptography and Data Security, San Juan, Jan 26-30, 2015. Cham: Sprin-ger, 2015: 528-547.
[16] 肖德琴, 张焕国, 胡月明, 等. 无线传感器网络攻击与防范[J]. 传感器与微系统, 2006, 25(8): 22-24.
XIAO D Q, ZHANG H G, HU Y M, et al. Attacks and defe-nses in wireless sensor network[J]. Transducer and Micro-system Technologies, 2006, 25(8): 22-24.
[17] YU H, GIBBONS P B, KAMINSKY M, et al. SybilLimit: a near-optimal social network defense against sybil attacks[J]. IEEE/ACM Transactions on Networking, 2010, 18(3): 885-898.
[18] 李忠诚, 黄建华, 唐瑞琮, 等. 一种基于权益代表的可扩展共识协议[J]. 应用科学学报, 2020, 38(1): 51-64.
LI Z C, HUANG J H, TANG R C, et al. A scalable con-sensus protocol based on stake representation[J]. Journal of Applied Sciences, 2020, 38(1): 51-64.
[19] 季钰翔, 黄建华, 王喆, 等. 基于信任度匹配的改进PBFT共识算法[J]. 计算机科学, 2021, 48(2): 303-310.
JI Y X, HUANG J H, WANG Z, et al. Improved PBFT consensus algorithm based on trust matching[J]. Computer Science, 2021, 48(2): 303-310.
[20] Intel? software guard extensions programming re-ference: Ref 329298-002[Z]. Intel, 2014: 1-6.