2022 Vol. 59 No. 4
2022, 59(4): 721-736.
DOI: 10.7544/issn1000-1239.20210231
Abstract：
Transactions provide strong guarantees for the upper-level applications based on databases and other systems. NoSQL databases obtain higher scalability by weakening the support for transactions, but it is difficult to meet the transactional requirements of applications such as OLTP. To retrieve the support for highly consistent transactions, the NewSQL database architecture proposed later takes into account the efficient management of massive data. NewSQL databases therefore migrate data accessed by transactions from disk to memory to accelerate transaction processing. However, existing concurrency control protocols of in-memory transactional systems are challenged by the incompatibility with emerging storage and network technology. We categorized the concurrency control protocols of in-memory transactions in the past ten years from the three dimensions of processing strategy, version control, and conflict resolution. Subsequently, we offer detailed comparisons of typical concurrency control protocols from the three aspects of performance, scalability, and durability. Then four technical solutions are summarized to improve concurrency control protocols of in-memory transactions including eliminating the bottleneck of scalability, accelerating transaction processing with emerging hardware, reducing the probability of transaction aborts and ensuring the durability of in-memory transactions efficiently. Finally, we point out the future research direction of concurrency control protocols of in-memory transactions.
Transactions provide strong guarantees for the upper-level applications based on databases and other systems. NoSQL databases obtain higher scalability by weakening the support for transactions, but it is difficult to meet the transactional requirements of applications such as OLTP. To retrieve the support for highly consistent transactions, the NewSQL database architecture proposed later takes into account the efficient management of massive data. NewSQL databases therefore migrate data accessed by transactions from disk to memory to accelerate transaction processing. However, existing concurrency control protocols of in-memory transactional systems are challenged by the incompatibility with emerging storage and network technology. We categorized the concurrency control protocols of in-memory transactions in the past ten years from the three dimensions of processing strategy, version control, and conflict resolution. Subsequently, we offer detailed comparisons of typical concurrency control protocols from the three aspects of performance, scalability, and durability. Then four technical solutions are summarized to improve concurrency control protocols of in-memory transactions including eliminating the bottleneck of scalability, accelerating transaction processing with emerging hardware, reducing the probability of transaction aborts and ensuring the durability of in-memory transactions efficiently. Finally, we point out the future research direction of concurrency control protocols of in-memory transactions.
2022, 59(4): 737-746.
DOI: 10.7544/issn1000-1239.20210140
Abstract：
The nested page table (NPT) model is an effective, hardware-assisted memory virtualization solution. However, the current Sunway processor lacks hardware support of NPT. However, the privileged programmable interface of Sunway architecture can be used to emulate the necessary hardware support with software. Hardware mode is the CPU privilege level unique to Sunway. This interface runs on the Sunway hardware mode with the highest CPU privileged level. In this paper, we propose the software-based flat nested page table (swFNPT) model for Sunway. In the programmable interface, we software-implement the hardware functions required by the nested page table model, such as nested page table walking. The new design makes up for the deficiency in hardware support through software optimization. In particular, the flat (one-level) nested page table is used to improve the efficiency of page walk. We use multiple benchmarks to test the performance of swFNPT. The experiments on a Sunway 1621 server show the promising performance of swFNPT. The average memory virtualization overhead of SPEC CPU 2006 is about 3% and the average overhead for SPEC CPU 2017 benchmarks with large working set is about 4%. The STREAM result shows that the memory bandwidth loss of swFNPT is less than 3%. Therefore, this paper provides a valuable reference for future development of hardware-assisted virtualization of Sunway server.
The nested page table (NPT) model is an effective, hardware-assisted memory virtualization solution. However, the current Sunway processor lacks hardware support of NPT. However, the privileged programmable interface of Sunway architecture can be used to emulate the necessary hardware support with software. Hardware mode is the CPU privilege level unique to Sunway. This interface runs on the Sunway hardware mode with the highest CPU privileged level. In this paper, we propose the software-based flat nested page table (swFNPT) model for Sunway. In the programmable interface, we software-implement the hardware functions required by the nested page table model, such as nested page table walking. The new design makes up for the deficiency in hardware support through software optimization. In particular, the flat (one-level) nested page table is used to improve the efficiency of page walk. We use multiple benchmarks to test the performance of swFNPT. The experiments on a Sunway 1621 server show the promising performance of swFNPT. The average memory virtualization overhead of SPEC CPU 2006 is about 3% and the average overhead for SPEC CPU 2017 benchmarks with large working set is about 4%. The STREAM result shows that the memory bandwidth loss of swFNPT is less than 3%. Therefore, this paper provides a valuable reference for future development of hardware-assisted virtualization of Sunway server.
2022, 59(4): 747-764.
DOI: 10.7544/issn1000-1239.20210203
Abstract：
Many industry field applications like industrial control, avionics, in-vehicle networks, and mobile prequel networks require deterministic low-latency network transmissions. In order to achieve these transmission requirements, the IEEE 802 time-sensitive networking (TSN) working group extends standard Ethernet to TSN, which attracts continuous attentions from both academia and industry. Traffic scheduling is the core mechanism in the TSN standard system, where the scheduling algorithm determines the transmission order and time period of each data frame on egress ports of all switches to meet the respective delay and bandwidth requirements of traffic and optimize transmission performance at the same time. In this paper, we first describe the formalization of traffic scheduling problem in TSN, introduce network and traffic models, and conclude the scheduling constraints and goals. A simple example is employed to illustrate the traffic scheduling task and procedure. Then we analyze and summarize existing TSN traffic scheduling mechanisms, focusing on their solved problems, concerned traffic type, optimized performance metrics and solving algorithms. Finally, the design space and development trends of future TSN traffic scheduling are discussed, and a novel idea of joint static traffic planning and dynamic traffic scheduling is proposed in response to the existing problems of current scheduling mechanisms.
Many industry field applications like industrial control, avionics, in-vehicle networks, and mobile prequel networks require deterministic low-latency network transmissions. In order to achieve these transmission requirements, the IEEE 802 time-sensitive networking (TSN) working group extends standard Ethernet to TSN, which attracts continuous attentions from both academia and industry. Traffic scheduling is the core mechanism in the TSN standard system, where the scheduling algorithm determines the transmission order and time period of each data frame on egress ports of all switches to meet the respective delay and bandwidth requirements of traffic and optimize transmission performance at the same time. In this paper, we first describe the formalization of traffic scheduling problem in TSN, introduce network and traffic models, and conclude the scheduling constraints and goals. A simple example is employed to illustrate the traffic scheduling task and procedure. Then we analyze and summarize existing TSN traffic scheduling mechanisms, focusing on their solved problems, concerned traffic type, optimized performance metrics and solving algorithms. Finally, the design space and development trends of future TSN traffic scheduling are discussed, and a novel idea of joint static traffic planning and dynamic traffic scheduling is proposed in response to the existing problems of current scheduling mechanisms.
2022, 59(4): 765-780.
DOI: 10.7544/issn1000-1239.20210644
Abstract：
The rapid popularity of the Internet of things has caused the scale of data to rise geometrically. The method of processing data concentrated in the cloud center gradually has problems such as communication delay and privacy leakage. Edge computing sinks part of the cloud center business to the edge of the device enabling data processing to be completed on the terminal network, thereby achieving rapid data processing. At the same time, as long-distance communication is avoided, user data can be transferred locally, so that user privacy data can be safely protected. However, the change of network architecture puts forward new requirements for security protocols in the edge computing environment. The classification and summary of security protocols in the edge computing environment is helpful to relevant practitioners quickly grasp the research progress in this field, and it will also help beginners in the field of edge computing security to quickly understand the application methods of security protocols in this field. The typical research results of authentication protocols, key agreement protocols, privacy-preserving protocols, and data sharing protocols in the edge computing environment are reviewed, and each kind of security protocols is specifically classified, analyzed and summarized. The core problems of security protocols in the edge computing environment are given, and specific research directions and suggestions are given for each protocol field. The purpose of overall grasp of the research progress of security protocols in the current edge computing environment is achieved.
The rapid popularity of the Internet of things has caused the scale of data to rise geometrically. The method of processing data concentrated in the cloud center gradually has problems such as communication delay and privacy leakage. Edge computing sinks part of the cloud center business to the edge of the device enabling data processing to be completed on the terminal network, thereby achieving rapid data processing. At the same time, as long-distance communication is avoided, user data can be transferred locally, so that user privacy data can be safely protected. However, the change of network architecture puts forward new requirements for security protocols in the edge computing environment. The classification and summary of security protocols in the edge computing environment is helpful to relevant practitioners quickly grasp the research progress in this field, and it will also help beginners in the field of edge computing security to quickly understand the application methods of security protocols in this field. The typical research results of authentication protocols, key agreement protocols, privacy-preserving protocols, and data sharing protocols in the edge computing environment are reviewed, and each kind of security protocols is specifically classified, analyzed and summarized. The core problems of security protocols in the edge computing environment are given, and specific research directions and suggestions are given for each protocol field. The purpose of overall grasp of the research progress of security protocols in the current edge computing environment is achieved.
2022, 59(4): 781-795.
DOI: 10.7544/issn1000-1239.20200620
Abstract：
Mobile edge computing (MEC) deploys computing and storage resources to the edge of the network, which brings real-time and high-reliability services to the Internet of vehicles (IoV). However, MEC faces various security threats. Attackers may control edge data centers and leak the pseudonym information of the vehicle, thereby threatening the vehicle’s identity privacy. For this problem, a vehicle pseudonym management scheme in MEC-IoV is proposed, which can realize efficient update of pseudonym information, secure storage of pseudonym information in the edge cloud, and traceability of pseudonyms. This scheme uses the edge cloud with high real-time performance to replace the central cloud to authenticate the vehicle identity, which improves the efficiency of identity authentication and realizes efficient pseudonym update. The pseudonym information is encrypted by the homomorphic encryption algorithm, which guarantees the security of the pseudonym information and doesn’t affect pseudonym management in the edge cloud. Each pseudonym table of the vehicle is associated with a search term calculated based on the pseudonym in the table, and the highest authority of the system can calculate the search term based on the ciphertext of the pseudonym table to expose the real identity of the malicious vehicle, which realize traceability of pseudonyms. After that, through the provable security theory, it is proved that the scheme is indistinguishable under the chosen plaintext attack, and the security analysis of the anonymity of the vehicle identity, the integrity and non-repudiation of the message in the scheme is carried out, which achieve the security requirements of preserving vehicle’s identity privacy in IoV. In the end, the efficiency analysis and simulation of the scheme in terms of identity authentication, pseudonym request, and homomorphic encryption performance are carried out. Experimental results show this scheme can achieve the requirements of low-latency communication in IoV and is superior to existing schemes in authentication efficiency.
Mobile edge computing (MEC) deploys computing and storage resources to the edge of the network, which brings real-time and high-reliability services to the Internet of vehicles (IoV). However, MEC faces various security threats. Attackers may control edge data centers and leak the pseudonym information of the vehicle, thereby threatening the vehicle’s identity privacy. For this problem, a vehicle pseudonym management scheme in MEC-IoV is proposed, which can realize efficient update of pseudonym information, secure storage of pseudonym information in the edge cloud, and traceability of pseudonyms. This scheme uses the edge cloud with high real-time performance to replace the central cloud to authenticate the vehicle identity, which improves the efficiency of identity authentication and realizes efficient pseudonym update. The pseudonym information is encrypted by the homomorphic encryption algorithm, which guarantees the security of the pseudonym information and doesn’t affect pseudonym management in the edge cloud. Each pseudonym table of the vehicle is associated with a search term calculated based on the pseudonym in the table, and the highest authority of the system can calculate the search term based on the ciphertext of the pseudonym table to expose the real identity of the malicious vehicle, which realize traceability of pseudonyms. After that, through the provable security theory, it is proved that the scheme is indistinguishable under the chosen plaintext attack, and the security analysis of the anonymity of the vehicle identity, the integrity and non-repudiation of the message in the scheme is carried out, which achieve the security requirements of preserving vehicle’s identity privacy in IoV. In the end, the efficiency analysis and simulation of the scheme in terms of identity authentication, pseudonym request, and homomorphic encryption performance are carried out. Experimental results show this scheme can achieve the requirements of low-latency communication in IoV and is superior to existing schemes in authentication efficiency.
2022, 59(4): 796-812.
DOI: 10.7544/issn1000-1239.20200779
Abstract：
Many popular social apps have the function of showing mutual relationship between users. However, the exposure of mutual relationship may lead to the occurrence of user privacy security problems. Taking China’s most famous short video software TikTok as the research object, a privacy disclosure security vulnerability in the mutual contacts function of TikTok is analyzed. A method of vulnerability exploiting and attacking for group users is proposed. The attack effect is that even if some users are not allowed to find themselves through their mobile phone numbers by some settings, an attacker can still use the known mobile phone numbers of group users and the internal connections among group users to get these users’ TikTok accounts. After getting as many TikTok accounts of the group users as possible, attackers can collect the following, contacts, video likes and comments information among group users, and use this information to calculate users’ relationship, which can provide some assistance for launching further effective attacks. Two indexes—intimacy and group-activeness—are proposed to describe users’ relationship, and the calculation method of these two indexes is given. Through the experiment of three real groups in society, the effectiveness of user relationship calculation is verified. In the end, the security threats to users are analyzed and the security prevention suggestions are given.
Many popular social apps have the function of showing mutual relationship between users. However, the exposure of mutual relationship may lead to the occurrence of user privacy security problems. Taking China’s most famous short video software TikTok as the research object, a privacy disclosure security vulnerability in the mutual contacts function of TikTok is analyzed. A method of vulnerability exploiting and attacking for group users is proposed. The attack effect is that even if some users are not allowed to find themselves through their mobile phone numbers by some settings, an attacker can still use the known mobile phone numbers of group users and the internal connections among group users to get these users’ TikTok accounts. After getting as many TikTok accounts of the group users as possible, attackers can collect the following, contacts, video likes and comments information among group users, and use this information to calculate users’ relationship, which can provide some assistance for launching further effective attacks. Two indexes—intimacy and group-activeness—are proposed to describe users’ relationship, and the calculation method of these two indexes is given. Through the experiment of three real groups in society, the effectiveness of user relationship calculation is verified. In the end, the security threats to users are analyzed and the security prevention suggestions are given.
2022, 59(4): 813-825.
DOI: 10.7544/issn1000-1239.20200565
Abstract：
In the mobile crowd sensing network, how to complete the sensing task assigned by the publisher within a limited time is an important problem faced by the mobile crowd sensing task distribution. To solve this problem, we propose a task distribution algorithm TDUATS based on user attention and time supervision in order to make the sensing users cooperate closely and feed back the sensing tasks to the sender in time. In the algorithm, the concepts of user attention, initial supervision, process supervision and completion supervision are proposed at first, and then the relationship between users who perform sensing tasks is analyzed. In order to monitor the process of task execution, the attention model among users is established, and the sensing tasks are distributed on this basis.Two real-world mobility datasets experiments demonstrate that the our proposed algorithm can not only complete the sensing task within a limited time, but also supervise the process of task execution, which is conductive to the publisher to timely understand the execution of the task, and plays a good role in improving the satisfaction of task execution. At the same time, compared with the comparison algorithms, sender and publisher can understand the task execution process in time, effectively improving the satisfaction of both parties.
In the mobile crowd sensing network, how to complete the sensing task assigned by the publisher within a limited time is an important problem faced by the mobile crowd sensing task distribution. To solve this problem, we propose a task distribution algorithm TDUATS based on user attention and time supervision in order to make the sensing users cooperate closely and feed back the sensing tasks to the sender in time. In the algorithm, the concepts of user attention, initial supervision, process supervision and completion supervision are proposed at first, and then the relationship between users who perform sensing tasks is analyzed. In order to monitor the process of task execution, the attention model among users is established, and the sensing tasks are distributed on this basis.Two real-world mobility datasets experiments demonstrate that the our proposed algorithm can not only complete the sensing task within a limited time, but also supervise the process of task execution, which is conductive to the publisher to timely understand the execution of the task, and plays a good role in improving the satisfaction of task execution. At the same time, compared with the comparison algorithms, sender and publisher can understand the task execution process in time, effectively improving the satisfaction of both parties.
2022, 59(4): 826-833.
DOI: 10.7544/issn1000-1239.20200662
Abstract：
In many practical applications of the Internet of things, the original collected signal data contains a lot of noise, especially in motion-related scenes. It is necessary to accurately identify the start and end points of the effective signal activity area from the one-dimensional time series signal with a lot of noise to support the relevant analysis. Existing recognition methods based on dual threshold rules are very sensitive to noise. The presence of noise will cause the calculated recognition threshold to fail to match the original data of the non-noise segment, which leads to the recognition of random noise data as signal activity intervals or missed signal activity interval. Recognition methods based on machine learning and deep learning require a large amount of sample data. In IoT scenarios with a small sample size, the model will have underfitting problems, thereby reducing recognition accuracy. In order to accurately identify the signal activity interval in a one-dimensional time series signal with a lot of noise and a small amount of data, a signal activity interval recognition based on local dynamic threshold EasiLTOM is proposed. This method calculates the recognition threshold based on the local signal, and it uses the shortest signal length to filter noise spikes, which can avoid the influence of random noise on the recognition of signal activity intervals, solve the problems of missed detection and false detection, and improve the recognition accuracy. In addition, EasiLTOM requires a small amount of data, which is suitable for IoT scenarios with scarce data. In order to verify the effectiveness of EasiLTOM, this study collects surface EMG data of 14 people in 3 months, and conducts comparative experiments using two public data sets. The results show that EasiLTOM method can achieve an average recognition accuracy of 93.17% for the signal activity range, which is 15.03% and 4.70% higher than the existing dual threshold and machine learning methods, and has practical value in motion analysis related scenes.
In many practical applications of the Internet of things, the original collected signal data contains a lot of noise, especially in motion-related scenes. It is necessary to accurately identify the start and end points of the effective signal activity area from the one-dimensional time series signal with a lot of noise to support the relevant analysis. Existing recognition methods based on dual threshold rules are very sensitive to noise. The presence of noise will cause the calculated recognition threshold to fail to match the original data of the non-noise segment, which leads to the recognition of random noise data as signal activity intervals or missed signal activity interval. Recognition methods based on machine learning and deep learning require a large amount of sample data. In IoT scenarios with a small sample size, the model will have underfitting problems, thereby reducing recognition accuracy. In order to accurately identify the signal activity interval in a one-dimensional time series signal with a lot of noise and a small amount of data, a signal activity interval recognition based on local dynamic threshold EasiLTOM is proposed. This method calculates the recognition threshold based on the local signal, and it uses the shortest signal length to filter noise spikes, which can avoid the influence of random noise on the recognition of signal activity intervals, solve the problems of missed detection and false detection, and improve the recognition accuracy. In addition, EasiLTOM requires a small amount of data, which is suitable for IoT scenarios with scarce data. In order to verify the effectiveness of EasiLTOM, this study collects surface EMG data of 14 people in 3 months, and conducts comparative experiments using two public data sets. The results show that EasiLTOM method can achieve an average recognition accuracy of 93.17% for the signal activity range, which is 15.03% and 4.70% higher than the existing dual threshold and machine learning methods, and has practical value in motion analysis related scenes.
2022, 59(4): 834-851.
DOI: 10.7544/issn1000-1239.20200673
Abstract：
Opportunistic network is a type of self-organized networks which uses the opportunity of a node moving to realize communication.Because of opportunistic communication mode, opportunistic network has observable time-varying and dynamic characteristics.The estimation of node importance is the key to study the information dissemination of opportunistic network.A novel node importance estimation method based on graph neural network (GNN-NIE) framework is proposed.Opportunistic network is sliced into opportunistic network units which is modeled by aggregate graph to present network information.The dynamic network embedding model is employed to extract the temporal and structural information among the opportunistic network units, so as to obtain the dynamic attribute features of each node in the network.Taking advantage of the GNN’s ability of extracting the features of graph data, the relationship between node dynamic attribute features and the node importance is achieved, so that the node importance of opportunistic network is estimated.The results on three real opportunistic network datasets MIT reality, Haggle project and Asturias-er show that compared with the temporal degree, temporal betweenness, temporal PageRank, and kshell-CN, the proposed method has faster propagation rate, larger message coverage and better SIR and NDCG@10 values.
Opportunistic network is a type of self-organized networks which uses the opportunity of a node moving to realize communication.Because of opportunistic communication mode, opportunistic network has observable time-varying and dynamic characteristics.The estimation of node importance is the key to study the information dissemination of opportunistic network.A novel node importance estimation method based on graph neural network (GNN-NIE) framework is proposed.Opportunistic network is sliced into opportunistic network units which is modeled by aggregate graph to present network information.The dynamic network embedding model is employed to extract the temporal and structural information among the opportunistic network units, so as to obtain the dynamic attribute features of each node in the network.Taking advantage of the GNN’s ability of extracting the features of graph data, the relationship between node dynamic attribute features and the node importance is achieved, so that the node importance of opportunistic network is estimated.The results on three real opportunistic network datasets MIT reality, Haggle project and Asturias-er show that compared with the temporal degree, temporal betweenness, temporal PageRank, and kshell-CN, the proposed method has faster propagation rate, larger message coverage and better SIR and NDCG@10 values.
2022, 59(4): 852-863.
DOI: 10.7544/issn1000-1239.20200976
Abstract：
In delay tolerant network (DTN), due to the frequent changes of network topology, there is no stable link between the end to end, so it is one of the key problems in DTN research to select the appropriate relay node for message forwarding and delivering the message to the destination node in a short time. Aiming at the blindness of relay node selection and the lack of reasonable control over message copies distribution in existing routing algorithms, an adaptive spray and wait routing algorithm based on comprehensive performance of node (CPN-ASW) is proposed: in spray phase, a new metric, called as node similarity, is used to measure the similarity degree of motion trajectory between nodes, and different relay node selection strategies are adopted according to whether the node similarity exceeds the given threshold value, and subsequently the number of message copies are adaptively allocated according to the relative utility value of nodes; in wait phase, an active forwarding strategy based on delivery probability is implemented, if a relay node has a lager delivery probability to the destination node, forwarding the message to this relay node. Simulation results show that compared with the Epidemic, Spray and Wait (SaW), EBR and PBSW, CPN-ASW can effectively control the network overhead while improving the delivery ratio and reducing the average delay.
In delay tolerant network (DTN), due to the frequent changes of network topology, there is no stable link between the end to end, so it is one of the key problems in DTN research to select the appropriate relay node for message forwarding and delivering the message to the destination node in a short time. Aiming at the blindness of relay node selection and the lack of reasonable control over message copies distribution in existing routing algorithms, an adaptive spray and wait routing algorithm based on comprehensive performance of node (CPN-ASW) is proposed: in spray phase, a new metric, called as node similarity, is used to measure the similarity degree of motion trajectory between nodes, and different relay node selection strategies are adopted according to whether the node similarity exceeds the given threshold value, and subsequently the number of message copies are adaptively allocated according to the relative utility value of nodes; in wait phase, an active forwarding strategy based on delivery probability is implemented, if a relay node has a lager delivery probability to the destination node, forwarding the message to this relay node. Simulation results show that compared with the Epidemic, Spray and Wait (SaW), EBR and PBSW, CPN-ASW can effectively control the network overhead while improving the delivery ratio and reducing the average delay.
2022, 59(4): 864-881.
DOI: 10.7544/issn1000-1239.20200767
Abstract：
In high performance computing, multicast operations supported by hardware have important impact on the performance of collective communication. As the supercomputer becomes larger and larger, the number of MCGs (multicast groups) increases rapidly also, and may exceed the number of MFT (multicast forwarding table) entries supported by hardware. However, the existing multicast routing algorithms do not provide solutions to this problem. This paper proposes a multicast routing algorithm for limited MFT size in InfiniBand called MR4LMS (multicast routing for limited MFT size). The algorithm uses two different methods, called FBTC (first build then color) and FCTB (first color then build) respectively, to build the multicast tree, in order to reduce the number of MFT entries as more as possible. When the number of MFT entries is not enough, several similar MCGs can be merged together by a merge algorithm to further reduce the required MFT entries. MR4LMS is tested under various typical topologies and communication patterns. The results show that it only needs 256 MFT entries to support thousands or even tens of thousands of MCGs to meet the requirements of typical communication patterns. In addition, we test the maximum EFI (edge forwarding index) and the running time of MR4LMS and obtain the satisfying performance result, which show that the MR4LMS can be used in large-scale interconnect networks.
In high performance computing, multicast operations supported by hardware have important impact on the performance of collective communication. As the supercomputer becomes larger and larger, the number of MCGs (multicast groups) increases rapidly also, and may exceed the number of MFT (multicast forwarding table) entries supported by hardware. However, the existing multicast routing algorithms do not provide solutions to this problem. This paper proposes a multicast routing algorithm for limited MFT size in InfiniBand called MR4LMS (multicast routing for limited MFT size). The algorithm uses two different methods, called FBTC (first build then color) and FCTB (first color then build) respectively, to build the multicast tree, in order to reduce the number of MFT entries as more as possible. When the number of MFT entries is not enough, several similar MCGs can be merged together by a merge algorithm to further reduce the required MFT entries. MR4LMS is tested under various typical topologies and communication patterns. The results show that it only needs 256 MFT entries to support thousands or even tens of thousands of MCGs to meet the requirements of typical communication patterns. In addition, we test the maximum EFI (edge forwarding index) and the running time of MR4LMS and obtain the satisfying performance result, which show that the MR4LMS can be used in large-scale interconnect networks.
2022, 59(4): 882-893.
DOI: 10.7544/issn1000-1239.20200986
Abstract：
With the maturity of UAV (unmanned aerial vehicle) technology, vehicles equipped with cameras are widely used in various fields, such as security and surveillance, aerial photography and infrastructure inspection. It is important to automatically and efficiently analyze and understand the visual data collected from vehicles. The object detection algorithm based on deep convolutional neural network has made amazing achievements in many practical applications, but it is often accompanied by great resource consumption and memory occupation. Thus, it is challenging to run deep convolutional neural networks directly on embedded devices with limited computing power carried by vehicles, which leads to high latency. In order to meet these challenges, a novel pruning algorithm based on iterative sparse training is proposed to improve the computational effectiveness of the classic object detection network YOLOv3 (you only look once). At the same time, different data enhancement methods and related optimization means are combined to ensure that the precision error of the detector before and after compression is within an acceptable range. Experimental results indicate that the pruning scheme based on iterative sparse training proposed in this paper achieves a considerable compression rate of YOLOv3 within slightly decline in precision. The original YOLOv3 model contains 61.57 MB weights and requires 139.77GFLOPS(floating-point operations). With 98.72% weights and 90.03% FLOPS reduced, our model still maintains a decent accuracy, with only 2.0% mAP(mean average precision) loss, which provides support for real-time application of UAV object detection.
With the maturity of UAV (unmanned aerial vehicle) technology, vehicles equipped with cameras are widely used in various fields, such as security and surveillance, aerial photography and infrastructure inspection. It is important to automatically and efficiently analyze and understand the visual data collected from vehicles. The object detection algorithm based on deep convolutional neural network has made amazing achievements in many practical applications, but it is often accompanied by great resource consumption and memory occupation. Thus, it is challenging to run deep convolutional neural networks directly on embedded devices with limited computing power carried by vehicles, which leads to high latency. In order to meet these challenges, a novel pruning algorithm based on iterative sparse training is proposed to improve the computational effectiveness of the classic object detection network YOLOv3 (you only look once). At the same time, different data enhancement methods and related optimization means are combined to ensure that the precision error of the detector before and after compression is within an acceptable range. Experimental results indicate that the pruning scheme based on iterative sparse training proposed in this paper achieves a considerable compression rate of YOLOv3 within slightly decline in precision. The original YOLOv3 model contains 61.57 MB weights and requires 139.77GFLOPS(floating-point operations). With 98.72% weights and 90.03% FLOPS reduced, our model still maintains a decent accuracy, with only 2.0% mAP(mean average precision) loss, which provides support for real-time application of UAV object detection.
2022, 59(4): 894-906.
DOI: 10.7544/issn1000-1239.20200915
Abstract：
Autonomous vehicles are the result of the combination of artificial intelligence and VANET. Because the autonomous vehicle can greatly free hands and improve traffic efficiency and safety, it has attracted wide attention of industry and researchers recently. While privacy issues such as instructions and vehicle identification have seriously hindered the application of autonomous car. The direct way to solve this problem is to expand the pseudonym-based communication schemes in VANET. However, most of these schemes not only impose a large storage burden on the vehicle but also fail to fully protect the identity privacy of the vehicle from being disclosed. In this paper, we propose an efficient and traceable anonymous VANET communication scheme for autonomous driving. In this scheme, a car is denoted by a set of attributes shared by multiple cars. Because of the one-to-many relationship between the attribute set and the vehicle, the anonymity of the vehicle is naturally realized. In addition, this scheme realizes the confidentiality of instructions and malicious vehicle tracking. In this paper, authentication encryption is integrated into attribute-based encryption scheme and a signcryption scheme is designed as the underlying technology to support the proposed anonymous communication scheme. Compared with the existing attribute-based signcryption schemes, this signcryption scheme is efficient and more suitable for automatic driving scenarios. Finally, the communication scheme is proved to be safe and efficient by formal security analysis and performance evaluation.
Autonomous vehicles are the result of the combination of artificial intelligence and VANET. Because the autonomous vehicle can greatly free hands and improve traffic efficiency and safety, it has attracted wide attention of industry and researchers recently. While privacy issues such as instructions and vehicle identification have seriously hindered the application of autonomous car. The direct way to solve this problem is to expand the pseudonym-based communication schemes in VANET. However, most of these schemes not only impose a large storage burden on the vehicle but also fail to fully protect the identity privacy of the vehicle from being disclosed. In this paper, we propose an efficient and traceable anonymous VANET communication scheme for autonomous driving. In this scheme, a car is denoted by a set of attributes shared by multiple cars. Because of the one-to-many relationship between the attribute set and the vehicle, the anonymity of the vehicle is naturally realized. In addition, this scheme realizes the confidentiality of instructions and malicious vehicle tracking. In this paper, authentication encryption is integrated into attribute-based encryption scheme and a signcryption scheme is designed as the underlying technology to support the proposed anonymous communication scheme. Compared with the existing attribute-based signcryption schemes, this signcryption scheme is efficient and more suitable for automatic driving scenarios. Finally, the communication scheme is proved to be safe and efficient by formal security analysis and performance evaluation.
2022, 59(4): 907-921.
DOI: 10.7544/issn1000-1239.20200897
Abstract：
In the process of clustering, the high-dimensionality and sparsity of multi-view data make the different features of samples described in a view have different effects on the clustering results, and each sample has different contributions to the clustering in different views. Hierarchically distinguishing the weights of different features in one view and the weights of the same sample in different views is an important factor to improve the quality of multi-view clustering. In this paper, we propose a multi-view clustering algorithm based on two-level weights, i.e. feature-level and sample-level weights. The proposed algorithm is named MVC2W, which learns the weights of different features in each view and the weights of each sample in different views by introducing a feature-level and a sample-level attention mechanism. The introduction of the two-level attention mechanism allows the algorithm to pay more attention to important features and important samples during the training process, and to integrate information from different views in a more rational way, thereby alleviating effectively the effects induced by high-dimensionality and sparsity on clustering quality. In addition, MVC2W integrates the process of representation learning and clustering into a unified framework for collaborative training and mutual promotion, so as to further improve the clustering performance. The experimental results on 5 datasets with different degrees of sparseness show that MVC2W algorithm outperforms 11 baseline algorithms, especially in the datasets with high degree of sparseness, and the improvement of clustering performance obtained by MVC2W is more significant.
In the process of clustering, the high-dimensionality and sparsity of multi-view data make the different features of samples described in a view have different effects on the clustering results, and each sample has different contributions to the clustering in different views. Hierarchically distinguishing the weights of different features in one view and the weights of the same sample in different views is an important factor to improve the quality of multi-view clustering. In this paper, we propose a multi-view clustering algorithm based on two-level weights, i.e. feature-level and sample-level weights. The proposed algorithm is named MVC2W, which learns the weights of different features in each view and the weights of each sample in different views by introducing a feature-level and a sample-level attention mechanism. The introduction of the two-level attention mechanism allows the algorithm to pay more attention to important features and important samples during the training process, and to integrate information from different views in a more rational way, thereby alleviating effectively the effects induced by high-dimensionality and sparsity on clustering quality. In addition, MVC2W integrates the process of representation learning and clustering into a unified framework for collaborative training and mutual promotion, so as to further improve the clustering performance. The experimental results on 5 datasets with different degrees of sparseness show that MVC2W algorithm outperforms 11 baseline algorithms, especially in the datasets with high degree of sparseness, and the improvement of clustering performance obtained by MVC2W is more significant.
2022, 59(4): 922-935.
DOI: 10.7544/issn1000-1239.20200875
Abstract：
Multi-view clustering is an important and challenged task due to the difficulty of integrating information from diverse views. After years of research it still faces two challenged questions to date. First, how to integrate heterogeneous information from different views effectively and reduce information loss. Second, how to perform graph learning and spectral clustering simultaneously, avoiding suboptimal clustering results caused by two-step strategy. Integrating heterogeneous information in the data space may cause significant information loss because of unavoidable noise hidden in the data itself or inconsistency among views. Moreover, we consider the case that different views admit the same cluster structure. To fill these gaps, a novel multi-view clustering model with spectral structure fusion is proposed, which fuses the information in the stage of spectral embedding. On the one hand, it avoids the influence of noise and difference of data from diverse views; on the other hand, the fusion position and method are more natural, which reduces the loss of information in the fusion stage. Besides, the model utilizes subspace self-representation for graph learning and integrates graph learning and spectral clustering into a unified framework effectively by joint optimization learning. Experiments on five widely used data sets confirm the superiority and validity of the proposed method.
Multi-view clustering is an important and challenged task due to the difficulty of integrating information from diverse views. After years of research it still faces two challenged questions to date. First, how to integrate heterogeneous information from different views effectively and reduce information loss. Second, how to perform graph learning and spectral clustering simultaneously, avoiding suboptimal clustering results caused by two-step strategy. Integrating heterogeneous information in the data space may cause significant information loss because of unavoidable noise hidden in the data itself or inconsistency among views. Moreover, we consider the case that different views admit the same cluster structure. To fill these gaps, a novel multi-view clustering model with spectral structure fusion is proposed, which fuses the information in the stage of spectral embedding. On the one hand, it avoids the influence of noise and difference of data from diverse views; on the other hand, the fusion position and method are more natural, which reduces the loss of information in the fusion stage. Besides, the model utilizes subspace self-representation for graph learning and integrates graph learning and spectral clustering into a unified framework effectively by joint optimization learning. Experiments on five widely used data sets confirm the superiority and validity of the proposed method.
2022, 59(4): 936-949.
DOI: 10.7544/issn1000-1239.20200879
Abstract：
Convolutional neural networks (CNNs)-based classification framework has achieved significant effects in pattern classification tasks, where the Softmax function with the cross-entropy loss (Softmax loss) can make CNNs learn separable embeddings. However, for some multi-classification problems, training with Softmax loss does not encourage increasing intra-class compactness and inter-class separability, which means it hardly generates the embedding with strong discriminability, making it hard to improve the performance further. In order to enhance the discriminability of learned embeddings, a cosine similarity-based Softmax (CS-Softmax) loss function is proposed. Without changing the network structure, the CS-Softmax loss introduces some parameters such as margin factor, scale factor and weight update factor to calculate the positive similarity and negative similarity between embeddings and different class weights based on the Softmax loss, so as to achieve the objectives of enhancing intra-class compactness and inter-class separability. Furthermore, the size of classification decision margin can be modified flexibly. These characteristics further enhance the discriminability of learned embeddings in CNNs. Classification experimental results on typical audio and image datasets show that the CS-Softmax loss can effectively improve the classification performance without increasing the computational complexity. The classification accuracies of the proposed loss are 99.81%, 95.46%, and 76.46% on the MNIST, CIFAR10, and CIFAR100 classification tasks, respectively.
Convolutional neural networks (CNNs)-based classification framework has achieved significant effects in pattern classification tasks, where the Softmax function with the cross-entropy loss (Softmax loss) can make CNNs learn separable embeddings. However, for some multi-classification problems, training with Softmax loss does not encourage increasing intra-class compactness and inter-class separability, which means it hardly generates the embedding with strong discriminability, making it hard to improve the performance further. In order to enhance the discriminability of learned embeddings, a cosine similarity-based Softmax (CS-Softmax) loss function is proposed. Without changing the network structure, the CS-Softmax loss introduces some parameters such as margin factor, scale factor and weight update factor to calculate the positive similarity and negative similarity between embeddings and different class weights based on the Softmax loss, so as to achieve the objectives of enhancing intra-class compactness and inter-class separability. Furthermore, the size of classification decision margin can be modified flexibly. These characteristics further enhance the discriminability of learned embeddings in CNNs. Classification experimental results on typical audio and image datasets show that the CS-Softmax loss can effectively improve the classification performance without increasing the computational complexity. The classification accuracies of the proposed loss are 99.81%, 95.46%, and 76.46% on the MNIST, CIFAR10, and CIFAR100 classification tasks, respectively.
