A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a (G), is the least number of colors in an acyclic edge coloring of G. Alon...A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a (G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a (G) Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a (G) max{2Δ(G) + 2, Δ(G) + 22} if g(G) 3, a (G) Δ(G) + 2 if g(G) 5, a (G) Δ(G) + 1 if g(G) 7, and a (G) = Δ(G) if g(G) 16 and Δ(G) 3. For series-parallel graphs G, we have a (G) Δ(G) + 1.展开更多
In the blockchain,the consensus mechanism plays a key role in maintaining the security and legitimation of contents recorded in the blocks.Various blockchain consensus mechanisms have been proposed.However,there is no...In the blockchain,the consensus mechanism plays a key role in maintaining the security and legitimation of contents recorded in the blocks.Various blockchain consensus mechanisms have been proposed.However,there is no technical analysis and comparison as a guideline to determine which type of consensus mechanism should be adopted in a specific scenario/application.To this end,this work investigates three mainstream consensus mechanisms in the blockchain,namely,Proof of Work(PoW),Proof of Stake(PoS),and Direct Acyclic Graph(DAG),and identifies their performances in terms of the average time to generate a new block,the confirmation delay,the Transaction Per Second(TPS)and the confirmation failure probability.The results show that the consensus process is affected by both network resource(computation power/coin age,buffer size)and network load conditions.In addition,it shows that PoW and PoS are more sensitive to the change of network resource while DAG is more sensitive to network load conditions.展开更多
A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if there exists a proper acyclic coloringπof G suc...A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if there exists a proper acyclic coloringπof G such thatπ(v)∈L(v)for all v∈V.If G is acyclically L-colorable for any list assignment L with|L(v)|k for all v∈V(G),then G is acyclically k-choosable.In this paper,we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i∈{3,4,5,6}.This improves the result by Wang and Chen(2009).展开更多
A proper edge k-coloring is a mappingΦ:E(G)-→{1,2,...,k}such that any two adjacent edges receive different colors.A proper edge k-coloringΦof G is called acyclic if there are no bichromatic cycles in G.The acyclic ...A proper edge k-coloring is a mappingΦ:E(G)-→{1,2,...,k}such that any two adjacent edges receive different colors.A proper edge k-coloringΦof G is called acyclic if there are no bichromatic cycles in G.The acyclic chromatic index of G,denoted by Xa(G),is the smallest integer k such that G is acyclically edge k-colorable.In this paper,we show that if G is a plane graph without 4-,6-cycles and intersecting 3-cycles,△(G)≥9,then Xa(G)≤△(G)+1.展开更多
The authors recently defined a new graph invariant denoted by Ω(G) only in terms of a given degree sequence which is also related to the Euler characteristic. It has many important combinatorial applications in graph...The authors recently defined a new graph invariant denoted by Ω(G) only in terms of a given degree sequence which is also related to the Euler characteristic. It has many important combinatorial applications in graph theory and gives direct information compared to the better known Euler characteristic on the realizability, connectedness, cyclicness, components, chords, loops etc. Many similar classification problems can be solved by means of Ω. All graphs G so that Ω(G) ≤-4 are shown to be disconnected, and if Ω(G) ≥-2, then the graph is potentially connected. It is also shown that if the realization is a connected graph and Ω(G) =-2, then certainly the graph should be a tree.Similarly, it is shown that if the realization is a connected graph G and Ω(G) ≥ 0, then certainly the graph should be cyclic. Also, when Ω(G) ≤-4, the components of the disconnected graph could not all be cyclic and if all the components of G are cyclic, then Ω(G) ≥ 0. In this paper, we study an extremal problem regarding graphs. We find the maximum number of loops for three possible classes of graphs.We also state a result giving the maximum number of components amongst all possible realizations of a given degree sequence.展开更多
The shock of the global financial crisis sparked widespread concern across the world about systemic financial risk and led to the reexamination of regulatory mechanisms.The traditional principle of“too big to fail”u...The shock of the global financial crisis sparked widespread concern across the world about systemic financial risk and led to the reexamination of regulatory mechanisms.The traditional principle of“too big to fail”underwent a transformation into the new idea of“too interconnected to fail.”We used Directed Acyclic Graph(DAG)technology and network topology analysis to examine the dynamic evolution of global systemic financial risk and the risk trends in global financial markets from the perspective of network connectivity.Our findings show that financial markets in the Chinese Mainland are net receivers of risk spillovers and that systemic financial risk has a clear cross-market contagion effect due to a global volatility spillover scale of 64 percent.To maintain the stability and security of China’s financial markets,consideration should be given to the regulatory precept of“too interconnected to fail”in establishing macro-prudential risk prevention mechanisms.展开更多
In view of the fact that current data delivery methods are not enough to meet the security requirements of today’s distributed crowd sensing,and the data delivery methods are not flexible enough,this paper proposes a...In view of the fact that current data delivery methods are not enough to meet the security requirements of today’s distributed crowd sensing,and the data delivery methods are not flexible enough,this paper proposes a crowd sensing data interaction method based on tangle directed acyclic graph(DAG)network.In this method,users and platforms are regarded as nodes of the network in the process of performing crowd sensing tasks.First,the heaviest chain is generated through the main chain strategy to ensure the stability of the network.Then,the hidden Markov model(HMM)prediction model is used to improve the correlation of the perceived data to improve the performance.Then,the confidential transaction and commitment algorithm is used to ensure the reliability of the transaction,overcome the security risks faced by the trusted third party,and simplify the group intelligence aware transaction mode.Finally,through simulation experiments,the security and feasibility of the group intelligence aware data delivery method based on tangle DAG network are verified.展开更多
In the past decade,blockchain has evolved as a promising solution to develop secure distributed ledgers and has gained massive attention.However,current blockchain systems face the problems of limited throughput,poor ...In the past decade,blockchain has evolved as a promising solution to develop secure distributed ledgers and has gained massive attention.However,current blockchain systems face the problems of limited throughput,poor scalability,and high latency.Due to the failure of consensus algorithms in managing nodes’identities,blockchain technology is considered inappropriate for many applications,e.g.,in IoT environments,because of poor scalability.This paper proposes a blockchain consensus mechanism called the Advanced DAG-based Ranking(ADR)protocol to improve blockchain scalability and throughput.The ADR protocol uses the directed acyclic graph ledger,where nodes are placed according to their ranking positions in the graph.It allows honest nodes to use theDirect Acyclic Graph(DAG)topology to write blocks and verify transactions instead of a chain of blocks.By using a three-step strategy,this protocol ensures that the system is secured against doublespending attacks and allows for higher throughput and scalability.The first step involves the safe entry of nodes into the system by verifying their private and public keys.The next step involves developing an advanced DAG ledger so nodes can start block production and verify transactions.In the third step,a ranking algorithm is developed to separate the nodes created by attackers.After eliminating attacker nodes,the nodes are ranked according to their performance in the system,and true nodes are arranged in blocks in topological order.As a result,the ADR protocol is suitable for applications in the Internet of Things(IoT).We evaluated ADR on EC2 clusters with more than 100 nodes and achieved better transaction throughput and liveness of the network while adding malicious nodes.Based on the simulation results,this research determined that the transaction’s performance was significantly improved over blockchains like Internet of Things Applications(IOTA)and ByteBall.展开更多
A proper edge coloring of a graph G is said to be acyclic if there is no bicolored cycle in G.The acyclic edge chromatic number of G,denoted byχ′a(G),is the smallest number of colors in an acyclic edge coloring of G...A proper edge coloring of a graph G is said to be acyclic if there is no bicolored cycle in G.The acyclic edge chromatic number of G,denoted byχ′a(G),is the smallest number of colors in an acyclic edge coloring of G.Let G be a planar graph with maximum degree.In this paper,we show thatχ′a(G)+2,if G has no adjacent i-and j-cycles for any i,j∈{3,4,5},which implies a result of Hou,Liu and Wu(2012);andχ′a(G)+3,if G has no adjacent i-and j-cycles for any i,j∈{3,4,6}.展开更多
Peer-to-peer(P2P)spectrum sharing and energy trading are promising solutions to locally satisfy spectrum and energy demands in power Internet of Things(IoT).However,implementation of largescale P2P spectrum sharing an...Peer-to-peer(P2P)spectrum sharing and energy trading are promising solutions to locally satisfy spectrum and energy demands in power Internet of Things(IoT).However,implementation of largescale P2P spectrum sharing and energy trading confronts security and privacy challenges.In this paper,we exploit consortium blockchain and Directed Acyclic Graph(DAG)to propose a new secure and distributed spectrum sharing and energy trading framework in power IoT,named spectrum-energy chain,where a set of local aggregators(LAGs)cooperatively confirm the identity of the power devices by utilizing consortium blockchain,so as to form a main chain.Then,the local power devices verify spectrum and energy micro-transactions simultaneously but asynchronously to form local spectrum tangle and local energy tangle,respectively.Moreover,an iterative double auction based micro transactions scheme is designed to solve the spectrum and energy pricing and the amount of shared spectrum and energy among power devices.Security analysis and numerical results illustrate that the developed spectrum-energy chain and the designed iterative double auction based microtransactions scheme are secure and efficient for spectrum sharing and energy trading in power IoT.展开更多
The wide application of intelligent terminals in microgrids has fueled the surge of data amount in recent years.In real-world scenarios,microgrids must store large amounts of data efficiently while also being able to ...The wide application of intelligent terminals in microgrids has fueled the surge of data amount in recent years.In real-world scenarios,microgrids must store large amounts of data efficiently while also being able to withstand malicious cyberattacks.To meet the high hardware resource requirements,address the vulnerability to network attacks and poor reliability in the tradi-tional centralized data storage schemes,this paper proposes a secure storage management method for microgrid data that considers node trust and directed acyclic graph(DAG)consensus mechanism.Firstly,the microgrid data storage model is designed based on the edge computing technology.The blockchain,deployed on the edge computing server and combined with cloud storage,ensures reliable data storage in the microgrid.Secondly,a blockchain consen-sus algorithm based on directed acyclic graph data structure is then proposed to effectively improve the data storage timeliness and avoid disadvantages in traditional blockchain topology such as long chain construction time and low consensus efficiency.Finally,considering the tolerance differences among the candidate chain-building nodes to network attacks,a hash value update mechanism of blockchain header with node trust identification to ensure data storage security is proposed.Experimental results from the microgrid data storage platform show that the proposed method can achieve a private key update time of less than 5 milliseconds.When the number of blockchain nodes is less than 25,the blockchain construction takes no more than 80 mins,and the data throughput is close to 300 kbps.Compared with the traditional chain-topology-based consensus methods that do not consider node trust,the proposed method has higher efficiency in data storage and better resistance to network attacks.展开更多
A proper coloring of a graphG is acyclic if G contains no 2-colored cycle.A graph G is acyclically L-list colorable if for a given list assignment L={L（v）：v∈V（G）},there exists a proper acyclic coloringφof G suc...A proper coloring of a graphG is acyclic if G contains no 2-colored cycle.A graph G is acyclically L-list colorable if for a given list assignment L={L（v）：v∈V（G）},there exists a proper acyclic coloringφof G such thatφ（v）∈L（v）for all v∈V（G）.If G is acyclically L-list colorable for any list assignment L with｜L（v）｜≥k for all v∈V（G）,then G is acyclically k-choosable.In this article,we prove that every toroidal graph is acyclically 8-choosable.展开更多
Due to the excellent performance in complex systems modeling under small samples and uncertainty,Belief Rule Base(BRB)expert system has been widely applied in fault diagnosis.However,the fault diagnosis process for co...Due to the excellent performance in complex systems modeling under small samples and uncertainty,Belief Rule Base(BRB)expert system has been widely applied in fault diagnosis.However,the fault diagnosis process for complex mechanical equipment normally needs multiple attributes,which can lead to the rule number explosion problem in BRB,and limit the efficiency and accuracy.To solve this problem,a novel Combination Belief Rule Base(C-BRB)model based on Directed Acyclic Graph(DAG)structure is proposed in this paper.By dispersing numerous attributes into the parallel structure composed of different sub-BRBs,C-BRB can effectively reduce the amount of calculation with acceptable result.At the same time,a path selection strategy considering the accuracy of child nodes is designed in C-BRB to obtain the most suitable submodels.Finally,a fusion method based on Evidential Reasoning(ER)rule is used to combine the belief rules of C-BRB and generate the final results.To illustrate the effectiveness and reliability of the proposed method,a case study of fault diagnosis of rolling bearing is conducted,and the result is compared with other methods.展开更多
In order to solve the problem of efficiently assigning tasks in an ad-hoc mobile cloud( AMC),a task assignment algorithm based on the heuristic algorithm is proposed. The proposed task assignment algorithm based on pa...In order to solve the problem of efficiently assigning tasks in an ad-hoc mobile cloud( AMC),a task assignment algorithm based on the heuristic algorithm is proposed. The proposed task assignment algorithm based on particle swarm optimization and simulated annealing( PSO-SA) transforms the dependencies between tasks into a directed acyclic graph( DAG) model. The number in each node represents the computation workload of each task and the number on each edge represents the workload produced by the transmission. In order to simulate the environment of task assignment in AMC,mathematical models are developed to describe the dependencies between tasks and the costs of each task are defined. PSO-SA is used to make the decision for task assignment and for minimizing the cost of all devices,which includes the energy consumption and time delay of all devices.PSO-SA also takes the advantage of both particle swarm optimization and simulated annealing by selecting an optimal solution with a certain probability to avoid falling into local optimal solution and to guarantee the convergence speed. The simulation results show that compared with other existing algorithms,the PSO-SA has a smaller cost and the result of PSO-SA can be very close to the optimal solution.展开更多
A k-colouring （not necessarily proper） of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We co...A k-colouring （not necessarily proper） of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclie k-eolourings such that each colour class induces a graph with a given （hereditary） property. In particular, we consider aeyclic k-eolourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyelic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree 4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with A（G） ≤ 4 can be acyelically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.展开更多
Mobile edge computing(MEC)is a promising technology for the Internet of Vehicles,especially in terms of application offloading and resource allocation.Most existing offloading schemes are sub-optimal,since these offlo...Mobile edge computing(MEC)is a promising technology for the Internet of Vehicles,especially in terms of application offloading and resource allocation.Most existing offloading schemes are sub-optimal,since these offloading strategies consider an application as a whole.In comparison,in this paper we propose an application-centric framework and build a finer-grained offloading scheme based on application partitioning.In our framework,each application is modelled as a directed acyclic graph,where each node represents a subtask and each edge represents the data flow dependency between a pair of subtasks.Both vehicles and MEC server within the communication range can be used as candidate offloading nodes.Then,the offloading involves assigning these computing nodes to subtasks.In addition,the proposed offloading scheme deal with the delay constraint of each subtask.The experimental evaluation show that,compared to existing non-partitioning offloading schemes,this proposed one effectively improves the performance of the application in terms of execution time and throughput.展开更多
Based on the key function of version management in PDM system, this paper discusses the function and the realization of version management and the transitions of version states with a workflow. A directed aeyclic grap...Based on the key function of version management in PDM system, this paper discusses the function and the realization of version management and the transitions of version states with a workflow. A directed aeyclic graph is used to describe a version model. Three storage modes of the directed acyelic graph version model in the database, the bumping block and the PDM working memory are presented and the conversion principle of these three modes is given. The study indicates that building a dynamic product structure configuration model based on versions is the key to resolve the problem. Thus a version model of single product object is built. Then the version management model in product structure configuration is built and the application of version management of PDM syster is presented as a case.展开更多
A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider...A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5 coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2 coloring in which each color class induces a graph with maximum degree at most 3 is NP complete, even for graphs with maximum degree 5. We also give a linear time algorithm for an acyclic t improper coloring of any graph with maximum degree d assuming that the number of colors is large enough.展开更多
An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors. The acyclic chromatic index of a graph G, denoted by a＇（G）, is the minimum numbe...An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors. The acyclic chromatic index of a graph G, denoted by a＇（G）, is the minimum number k such that there is an acyclic edge coloring using k colors. It is known that a＇（G） ≤ 16△ for every graph G where △denotes the maximum degree of G. We prove that a＇（G） 〈 13.8A for an arbitrary graph G. We also reduce the upper bounds of a＇（G） to 9.8△ and 9△ with girth 5 and 7, respectively.展开更多
Inspired by previous work of Diaz, Petit, Serna, and Trevisan (Approximating layout problems on random graphs, Discrete Mathematics, 235, 2001, 245-253), we show that several well-known graph layout problems are appro...Inspired by previous work of Diaz, Petit, Serna, and Trevisan (Approximating layout problems on random graphs, Discrete Mathematics, 235, 2001, 245-253), we show that several well-known graph layout problems are approximable to within a factor arbitrarily close to 1 of the optimal with high probability for random graphs drawn from an Erdös-Renyi distribution with appropriate sparsity conditions using only elementary probabilistic analysis. Moreover, we show that the same results hold for the analogous problems on directed acyclic graphs.展开更多
基金supported by National Natural Science Foundation of China (Grant No. 10871119)NaturalScience Foundation of Shandong Province (Grant No. Y2008A20).
文摘A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a (G), is the least number of colors in an acyclic edge coloring of G. Alon et al. conjectured that a (G) Δ(G) + 2 for any graphs. For planar graphs G with girth g(G), we prove that a (G) max{2Δ(G) + 2, Δ(G) + 22} if g(G) 3, a (G) Δ(G) + 2 if g(G) 5, a (G) Δ(G) + 1 if g(G) 7, and a (G) = Δ(G) if g(G) 16 and Δ(G) 3. For series-parallel graphs G, we have a (G) Δ(G) + 1.
基金the National Natural Science Foundation of China under Grant 61701059,Grant 61941114,and Grant 61831002,in part by the Fundamental Research Funds for the Central Universities of New TeachersProject,in part by the Chongqing Technological Innovation and Application Development Projects under Grant cstc2019jscx-msxm1322,and in part by the Eighteentg Open Foundation of State Key Lab of Integrated Services Networks of Xidian University under Grant ISN20-05.
文摘In the blockchain,the consensus mechanism plays a key role in maintaining the security and legitimation of contents recorded in the blocks.Various blockchain consensus mechanisms have been proposed.However,there is no technical analysis and comparison as a guideline to determine which type of consensus mechanism should be adopted in a specific scenario/application.To this end,this work investigates three mainstream consensus mechanisms in the blockchain,namely,Proof of Work(PoW),Proof of Stake(PoS),and Direct Acyclic Graph(DAG),and identifies their performances in terms of the average time to generate a new block,the confirmation delay,the Transaction Per Second(TPS)and the confirmation failure probability.The results show that the consensus process is affected by both network resource(computation power/coin age,buffer size)and network load conditions.In addition,it shows that PoW and PoS are more sensitive to the change of network resource while DAG is more sensitive to network load conditions.
基金supported by National Natural Science Foundation of China (Grant Nos. 11071223 and 11101377)Natural Science Foundation of Zhejiang Province,China (Gran No. Z6090150)+1 种基金Zhejiang Innovation Project (Grant No. T200905)Zhejiang Normal University Innovation Team Program
文摘A proper vertex coloring of a graph G is acyclic if G contains no bicolored cycles.Given a list assignment L={L(v)|v∈V}of G,we say that G is acyclically L-colorable if there exists a proper acyclic coloringπof G such thatπ(v)∈L(v)for all v∈V.If G is acyclically L-colorable for any list assignment L with|L(v)|k for all v∈V(G),then G is acyclically k-choosable.In this paper,we prove that every planar graph G is acyclically 6-choosable if G does not contain 4-cycles adjacent to i-cycles for each i∈{3,4,5,6}.This improves the result by Wang and Chen(2009).
文摘A proper edge k-coloring is a mappingΦ:E(G)-→{1,2,...,k}such that any two adjacent edges receive different colors.A proper edge k-coloringΦof G is called acyclic if there are no bichromatic cycles in G.The acyclic chromatic index of G,denoted by Xa(G),is the smallest integer k such that G is acyclically edge k-colorable.In this paper,we show that if G is a plane graph without 4-,6-cycles and intersecting 3-cycles,△(G)≥9,then Xa(G)≤△(G)+1.
文摘The authors recently defined a new graph invariant denoted by Ω(G) only in terms of a given degree sequence which is also related to the Euler characteristic. It has many important combinatorial applications in graph theory and gives direct information compared to the better known Euler characteristic on the realizability, connectedness, cyclicness, components, chords, loops etc. Many similar classification problems can be solved by means of Ω. All graphs G so that Ω(G) ≤-4 are shown to be disconnected, and if Ω(G) ≥-2, then the graph is potentially connected. It is also shown that if the realization is a connected graph and Ω(G) =-2, then certainly the graph should be a tree.Similarly, it is shown that if the realization is a connected graph G and Ω(G) ≥ 0, then certainly the graph should be cyclic. Also, when Ω(G) ≤-4, the components of the disconnected graph could not all be cyclic and if all the components of G are cyclic, then Ω(G) ≥ 0. In this paper, we study an extremal problem regarding graphs. We find the maximum number of loops for three possible classes of graphs.We also state a result giving the maximum number of components amongst all possible realizations of a given degree sequence.
基金the phased result of “Research on Systematic Financial Risk Prevention Mechanisms in China Based on Structured Data Analysis”(17ZDA073)a major project of the National Social Science Fund of China.
文摘The shock of the global financial crisis sparked widespread concern across the world about systemic financial risk and led to the reexamination of regulatory mechanisms.The traditional principle of“too big to fail”underwent a transformation into the new idea of“too interconnected to fail.”We used Directed Acyclic Graph(DAG)technology and network topology analysis to examine the dynamic evolution of global systemic financial risk and the risk trends in global financial markets from the perspective of network connectivity.Our findings show that financial markets in the Chinese Mainland are net receivers of risk spillovers and that systemic financial risk has a clear cross-market contagion effect due to a global volatility spillover scale of 64 percent.To maintain the stability and security of China’s financial markets,consideration should be given to the regulatory precept of“too interconnected to fail”in establishing macro-prudential risk prevention mechanisms.
文摘In view of the fact that current data delivery methods are not enough to meet the security requirements of today’s distributed crowd sensing,and the data delivery methods are not flexible enough,this paper proposes a crowd sensing data interaction method based on tangle directed acyclic graph(DAG)network.In this method,users and platforms are regarded as nodes of the network in the process of performing crowd sensing tasks.First,the heaviest chain is generated through the main chain strategy to ensure the stability of the network.Then,the hidden Markov model(HMM)prediction model is used to improve the correlation of the perceived data to improve the performance.Then,the confidential transaction and commitment algorithm is used to ensure the reliability of the transaction,overcome the security risks faced by the trusted third party,and simplify the group intelligence aware transaction mode.Finally,through simulation experiments,the security and feasibility of the group intelligence aware data delivery method based on tangle DAG network are verified.
文摘In the past decade,blockchain has evolved as a promising solution to develop secure distributed ledgers and has gained massive attention.However,current blockchain systems face the problems of limited throughput,poor scalability,and high latency.Due to the failure of consensus algorithms in managing nodes’identities,blockchain technology is considered inappropriate for many applications,e.g.,in IoT environments,because of poor scalability.This paper proposes a blockchain consensus mechanism called the Advanced DAG-based Ranking(ADR)protocol to improve blockchain scalability and throughput.The ADR protocol uses the directed acyclic graph ledger,where nodes are placed according to their ranking positions in the graph.It allows honest nodes to use theDirect Acyclic Graph(DAG)topology to write blocks and verify transactions instead of a chain of blocks.By using a three-step strategy,this protocol ensures that the system is secured against doublespending attacks and allows for higher throughput and scalability.The first step involves the safe entry of nodes into the system by verifying their private and public keys.The next step involves developing an advanced DAG ledger so nodes can start block production and verify transactions.In the third step,a ranking algorithm is developed to separate the nodes created by attackers.After eliminating attacker nodes,the nodes are ranked according to their performance in the system,and true nodes are arranged in blocks in topological order.As a result,the ADR protocol is suitable for applications in the Internet of Things(IoT).We evaluated ADR on EC2 clusters with more than 100 nodes and achieved better transaction throughput and liveness of the network while adding malicious nodes.Based on the simulation results,this research determined that the transaction’s performance was significantly improved over blockchains like Internet of Things Applications(IOTA)and ByteBall.
基金supported by National Natural Science Foundation of China(Grant Nos.10931003 and 11171160)by Doctoral Fund of Ministry of Education of China(Grant No.10871011)
文摘A proper edge coloring of a graph G is said to be acyclic if there is no bicolored cycle in G.The acyclic edge chromatic number of G,denoted byχ′a(G),is the smallest number of colors in an acyclic edge coloring of G.Let G be a planar graph with maximum degree.In this paper,we show thatχ′a(G)+2,if G has no adjacent i-and j-cycles for any i,j∈{3,4,5},which implies a result of Hou,Liu and Wu(2012);andχ′a(G)+3,if G has no adjacent i-and j-cycles for any i,j∈{3,4,6}.
基金supported by the National Key R&D Program of China(2020YFB1807801,2020YFB1807800)in part by Project Supported by Engineering Research Center of Mobile Communications,Ministry of Education(cqupt-mct-202003)+2 种基金in part by Key Lab of Information Network Security,Ministry of Public Security under Grant C19603in part by National Natural Science Foundation of China(Grant No.61901067 and 61901013)in part by Chongqing Municipal Natural Science Foundation(Grant No.cstc2020jcyj-msxmX0339).
文摘Peer-to-peer(P2P)spectrum sharing and energy trading are promising solutions to locally satisfy spectrum and energy demands in power Internet of Things(IoT).However,implementation of largescale P2P spectrum sharing and energy trading confronts security and privacy challenges.In this paper,we exploit consortium blockchain and Directed Acyclic Graph(DAG)to propose a new secure and distributed spectrum sharing and energy trading framework in power IoT,named spectrum-energy chain,where a set of local aggregators(LAGs)cooperatively confirm the identity of the power devices by utilizing consortium blockchain,so as to form a main chain.Then,the local power devices verify spectrum and energy micro-transactions simultaneously but asynchronously to form local spectrum tangle and local energy tangle,respectively.Moreover,an iterative double auction based micro transactions scheme is designed to solve the spectrum and energy pricing and the amount of shared spectrum and energy among power devices.Security analysis and numerical results illustrate that the developed spectrum-energy chain and the designed iterative double auction based microtransactions scheme are secure and efficient for spectrum sharing and energy trading in power IoT.
文摘The wide application of intelligent terminals in microgrids has fueled the surge of data amount in recent years.In real-world scenarios,microgrids must store large amounts of data efficiently while also being able to withstand malicious cyberattacks.To meet the high hardware resource requirements,address the vulnerability to network attacks and poor reliability in the tradi-tional centralized data storage schemes,this paper proposes a secure storage management method for microgrid data that considers node trust and directed acyclic graph(DAG)consensus mechanism.Firstly,the microgrid data storage model is designed based on the edge computing technology.The blockchain,deployed on the edge computing server and combined with cloud storage,ensures reliable data storage in the microgrid.Secondly,a blockchain consen-sus algorithm based on directed acyclic graph data structure is then proposed to effectively improve the data storage timeliness and avoid disadvantages in traditional blockchain topology such as long chain construction time and low consensus efficiency.Finally,considering the tolerance differences among the candidate chain-building nodes to network attacks,a hash value update mechanism of blockchain header with node trust identification to ensure data storage security is proposed.Experimental results from the microgrid data storage platform show that the proposed method can achieve a private key update time of less than 5 milliseconds.When the number of blockchain nodes is less than 25,the blockchain construction takes no more than 80 mins,and the data throughput is close to 300 kbps.Compared with the traditional chain-topology-based consensus methods that do not consider node trust,the proposed method has higher efficiency in data storage and better resistance to network attacks.
基金supported by National Natural Science Foundation of China(Grant No.11001055)supported by National Natural Science Foundation of China(Grant No.60672030)Natural Science Foundation of Fujian Province(Grant Nos.2010J05004 and 2011J06001)
文摘A proper coloring of a graphG is acyclic if G contains no 2-colored cycle.A graph G is acyclically L-list colorable if for a given list assignment L={L（v）：v∈V（G）},there exists a proper acyclic coloringφof G such thatφ（v）∈L（v）for all v∈V（G）.If G is acyclically L-list colorable for any list assignment L with｜L（v）｜≥k for all v∈V（G）,then G is acyclically k-choosable.In this article,we prove that every toroidal graph is acyclically 8-choosable.
基金supported by the Natural Science Foundation of China(Nos.61773388,61751304,61833016,61702142,U1811264 and 61966009)the Shaanxi Outstanding Youth Science Foundation,China(No.2020JC-34)+2 种基金the Key Research and Development Plan of Hainan,China(No.ZDYF2019007)China Postdoctoral Science Foundation(No.2020M673668)Guangxi Key Laboratory of Trusted Software,China(No.KX202050)。
文摘Due to the excellent performance in complex systems modeling under small samples and uncertainty,Belief Rule Base(BRB)expert system has been widely applied in fault diagnosis.However,the fault diagnosis process for complex mechanical equipment normally needs multiple attributes,which can lead to the rule number explosion problem in BRB,and limit the efficiency and accuracy.To solve this problem,a novel Combination Belief Rule Base(C-BRB)model based on Directed Acyclic Graph(DAG)structure is proposed in this paper.By dispersing numerous attributes into the parallel structure composed of different sub-BRBs,C-BRB can effectively reduce the amount of calculation with acceptable result.At the same time,a path selection strategy considering the accuracy of child nodes is designed in C-BRB to obtain the most suitable submodels.Finally,a fusion method based on Evidential Reasoning(ER)rule is used to combine the belief rules of C-BRB and generate the final results.To illustrate the effectiveness and reliability of the proposed method,a case study of fault diagnosis of rolling bearing is conducted,and the result is compared with other methods.
基金The National Natural Science Foundation of China(No.61741102,61471164,61601122)the Fundamental Research Funds for the Central Universities(No.SJLX_160040)
文摘In order to solve the problem of efficiently assigning tasks in an ad-hoc mobile cloud( AMC),a task assignment algorithm based on the heuristic algorithm is proposed. The proposed task assignment algorithm based on particle swarm optimization and simulated annealing( PSO-SA) transforms the dependencies between tasks into a directed acyclic graph( DAG) model. The number in each node represents the computation workload of each task and the number on each edge represents the workload produced by the transmission. In order to simulate the environment of task assignment in AMC,mathematical models are developed to describe the dependencies between tasks and the costs of each task are defined. PSO-SA is used to make the decision for task assignment and for minimizing the cost of all devices,which includes the energy consumption and time delay of all devices.PSO-SA also takes the advantage of both particle swarm optimization and simulated annealing by selecting an optimal solution with a certain probability to avoid falling into local optimal solution and to guarantee the convergence speed. The simulation results show that compared with other existing algorithms,the PSO-SA has a smaller cost and the result of PSO-SA can be very close to the optimal solution.
基金supported by the Minister of Science and Higher Education of Poland(Grant No.JP2010009070)
文摘A k-colouring （not necessarily proper） of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclie k-eolourings such that each colour class induces a graph with a given （hereditary） property. In particular, we consider aeyclic k-eolourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyelic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree 4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with A（G） ≤ 4 can be acyelically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.
基金This work was supported by the National Natural Science Foundation of China(Grant Nos.U20A20177,61772377,91746206)the Fundamental Research Funds for the Central Universities,and Science and Technology planning project of ShenZhen(JCYJ20170818112550194).
文摘Mobile edge computing(MEC)is a promising technology for the Internet of Vehicles,especially in terms of application offloading and resource allocation.Most existing offloading schemes are sub-optimal,since these offloading strategies consider an application as a whole.In comparison,in this paper we propose an application-centric framework and build a finer-grained offloading scheme based on application partitioning.In our framework,each application is modelled as a directed acyclic graph,where each node represents a subtask and each edge represents the data flow dependency between a pair of subtasks.Both vehicles and MEC server within the communication range can be used as candidate offloading nodes.Then,the offloading involves assigning these computing nodes to subtasks.In addition,the proposed offloading scheme deal with the delay constraint of each subtask.The experimental evaluation show that,compared to existing non-partitioning offloading schemes,this proposed one effectively improves the performance of the application in terms of execution time and throughput.
基金the Scientific Technology Development Project of Heilongjiang(Grant No.WH05A01 and GB05A103)Scientific Technology Development Project of Harbin
文摘Based on the key function of version management in PDM system, this paper discusses the function and the realization of version management and the transitions of version states with a workflow. A directed aeyclic graph is used to describe a version model. Three storage modes of the directed acyelic graph version model in the database, the bumping block and the PDM working memory are presented and the conversion principle of these three modes is given. The study indicates that building a dynamic product structure configuration model based on versions is the key to resolve the problem. Thus a version model of single product object is built. Then the version management model in product structure configuration is built and the application of version management of PDM syster is presented as a case.
基金supported by the Minister of Science and Higher Education of Poland (Grant No. JP2010009070)
文摘A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5 coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2 coloring in which each color class induces a graph with maximum degree at most 3 is NP complete, even for graphs with maximum degree 5. We also give a linear time algorithm for an acyclic t improper coloring of any graph with maximum degree d assuming that the number of colors is large enough.
基金Supported by the National Natural Science Foundation of China(No.11371355)
文摘An acyclic edge coloring of a graph is a proper edge coloring such that every cycle contains edges of at least three distinct colors. The acyclic chromatic index of a graph G, denoted by a＇（G）, is the minimum number k such that there is an acyclic edge coloring using k colors. It is known that a＇（G） ≤ 16△ for every graph G where △denotes the maximum degree of G. We prove that a＇（G） 〈 13.8A for an arbitrary graph G. We also reduce the upper bounds of a＇（G） to 9.8△ and 9△ with girth 5 and 7, respectively.
文摘Inspired by previous work of Diaz, Petit, Serna, and Trevisan (Approximating layout problems on random graphs, Discrete Mathematics, 235, 2001, 245-253), we show that several well-known graph layout problems are approximable to within a factor arbitrarily close to 1 of the optimal with high probability for random graphs drawn from an Erdös-Renyi distribution with appropriate sparsity conditions using only elementary probabilistic analysis. Moreover, we show that the same results hold for the analogous problems on directed acyclic graphs.
