Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Decentralized connectivity-aware computational resource sharing system in the D2D networks Hong, Zhen 2019

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


24-ubc_2020_may_hong_zhen.pdf [ 1.71MB ]
JSON: 24-1.0384550.json
JSON-LD: 24-1.0384550-ld.json
RDF/XML (Pretty): 24-1.0384550-rdf.xml
RDF/JSON: 24-1.0384550-rdf.json
Turtle: 24-1.0384550-turtle.txt
N-Triples: 24-1.0384550-rdf-ntriples.txt
Original Record: 24-1.0384550-source.json
Full Text

Full Text

Decentralized Connectivity-Aware ComputationalResource Sharing System in the D2D NetworksbyZhen HongB.A.Sc., The University of British Columbia, 2015A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFMaster of Applied ScienceinTHE FACULTY OF GRADUATE AND POSTDOCTORALSTUDIES(Electrical and Computer Engineering)The University of British Columbia(Vancouver)October 2019c© Zhen Hong, 2019The following individuals certify that they have read, and recommend to the Faculty ofGraduate and Postdoctoral Studies for acceptance, the thesis entitled:Decentralized Connectivity-Aware Computational Resource SharingSystem in the D2D Networkssubmitted by Zhen Hong in partial fulfillment of the requirements for the degree of Masterof Applied Science in Electrical and Computer Engineering.Examining Committee:Victor C.M. LeungSupervisorPanos NasiopoulosSupervisory Committee MemberChen FengSupervisory Committee MemberiiAbstractDevice-to-device (D2D) communication and its applications are increasingly important infuture networks with the climbing demand for rapid local services. Specifically, resourcesharing in the D2D networks is featured by the ubiquitous availability, flexibility, low-latency and low-cost. However, there are challenges when building a satisfactory resourcesharing system in the D2D networks, including user mobility and proper incentives forusers to share. Previous endeavors typically are not comprehensive over mobility consid-eration, fairness, and efficiency. In this thesis, we introduce a decentralized connectivity-aware computational resource sharing system in the D2D networks.Three steps are taken towards building such system: 1) an innovative connectivity-aware task scheduling paradigm is proposed to help a user to outsource appropriateamount of computational tasks to appropriate users at appropriate time; 2) a decentralizedblockchain-based ledger system is introduced to reduce selfishness; 3) a directed acyclicgraph (DAG) based ledger system is proposed to avoid notorious monetary and time costsin a traditional proof of work (PoW) based ledger system, which realizes our decentralizedsharing system.Mobility and fairness considerations are formulated as optimization problems with sys-tem designs and light-weight algorithms presented. We carried out simulations based onreal connectivity traces, and the results show that consideration of mobility can further re-duce average task execution time and sacrificing a minor amount of execution time getsiiimajor enhance in fairness.High transaction fees, long confirmation time, and thus low efficiency are notoriousissues in traditional PoW-based blockchain systems. Many blockchain companies withmulti-billion market cap, e.g. IOTA and Nano, believe that properly designed DAG-basedledger systems are the best candidates to achieve very high transaction throughput. Inspiredby existing DAG-based ledger technology, our efficiency consideration is mainly a designof a novel decentralized DAG-based ledger system that is suitable to our D2D system forhigh transaction throughput and solves the aforementioned issues in a traditional PoW-baseledger system. We simulated decentralized systems according to specifications in the IOTAwhitepaper, and simulation results show that our system is much more realistic and suitableto a D2D system that needs high throughput, even compared to the leading pioneers likeIOTA.ivLay SummaryIt is not surprising to see numerous spare smart devices in crowed places like libraries andrestaurants. In fact, studies showed that, on average, less than 50% of computing powergets utilized by smart devices even under active usage. Challenges behind sharing mo-bile computing power include unstable connections and selfish users that take help fromneighbors but never share back. Hence, this thesis proposed novel mechanisms to tackleconnection and fairness issues. Recent rage in Bitcoin is urging people to realize the impor-tance of a decentralized ledger system where every member, instead of a central authority,participates in maintaining the shared ledger. Inspired by that, we also designed a noveldecentralized credit system that precludes central authority from manipulating or makingfatal mistakes. Simulation results show that computing power can be shared more effec-tively and fairly, and our mechanism to maintain the credit system is much less costly thanthose proposed by even the leading pioneers like IOTA.vPrefaceThis thesis is based on the research I conducted under the supervision of Prof. Victor C.M.Leung. The result of this research was several articles that have been accepted or to bepublished. I developed and implemented the ideas for these articles under the supervi-sion of Prof. Leung and the collaboration with Dr. Zehua Wang and Dr. Wei Cai. Thecollaborators’ contributions are listed as follows:1. Dr. Zehua Wang provided helpful suggestions for improving the articles related toChapters 2-4 and validated the analyses.2. Dr. Wei Cai helped me in analyzing the simulation results of the articles related toChapters 2-3.One article is published for the work in each of Chapter 2 and Chapter 3. The articlerelated to Chapter 4 is under preparation and has yet to be submitted. I hereby declare thatI am the first author of this thesis and articles corresponding to Chapters 2-4. Publicationsaccomplished are listed as follows:• Chapter 2: Zhen Hong, Zehua Wang, Wei Cai, and Victor C.M. Leung,“Connectivity-Aware Task Outsourcing and Scheduling in D2D Networks,” 201726th International Conference on Computer Communication and Networks (IC-CCN), Vancouver, BC, 2017, pp.• Chapter 3: Zhen Hong, Zehua Wang, Wei Cai, and Victor C.M. Leung, “Blockchain-Empowered Fair Computational Resource Sharing System in the D2D Network,”Future Internet 2017, 9, 85.• Chapter 4: Zhen Hong, Zehua Wang, and Victor C.M. Leung, “The Buffer Mecha-nism for a DAG-Based Decentralized Ledger System,” pending submission.viiTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiGlossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xviiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .xviii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Background and Related Work . . . . . . . . . . . . . . . . . . . . . . . . 11.1.1 Fog Computing and the D2D Networks . . . . . . . . . . . . . . . 31.1.2 Blockchain and Distributed Ledger Technology . . . . . . . . . . . 61.1.3 DAG-Based Decentralized Ledger Systems . . . . . . . . . . . . . 10viii1.2 Motivation and Research Questions . . . . . . . . . . . . . . . . . . . . . . 111.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.4 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Connectivity-Aware Task Outsourcing and Scheduling . . . . . . . . . . . . . 142.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142.2 System Modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.2.1 Basic System Settings . . . . . . . . . . . . . . . . . . . . . . . . . 162.2.2 Connectivity Model . . . . . . . . . . . . . . . . . . . . . . . . . . 172.2.3 Dynamic Program Slicing . . . . . . . . . . . . . . . . . . . . . . 192.2.4 Task Cooperation Scheduling . . . . . . . . . . . . . . . . . . . . . 202.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.3.1 Connectivity Awareness . . . . . . . . . . . . . . . . . . . . . . . 212.3.2 Computation Assignment and Maximum Wait Time . . . . . . . . . 222.3.3 Computational Capacity of Mobile Devices . . . . . . . . . . . . . 222.3.4 Response Delay Optimization . . . . . . . . . . . . . . . . . . . . 232.3.5 Overall Optimization Problem . . . . . . . . . . . . . . . . . . . . 242.4 Experiment and Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . 252.4.1 Number of Requesters . . . . . . . . . . . . . . . . . . . . . . . . 262.4.2 Number of Helpers . . . . . . . . . . . . . . . . . . . . . . . . . . 282.4.3 Mean Maximum Wait Time . . . . . . . . . . . . . . . . . . . . . . 302.4.4 Mean Task Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343 Decentralized Ledger System and Selfishness Avoidance . . . . . . . . . . . . 363.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.2 System Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37ix3.2.1 Blockchain Ledger Basics . . . . . . . . . . . . . . . . . . . . . . 383.2.2 Design Specifics . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.2.3 Overall Working Process . . . . . . . . . . . . . . . . . . . . . . . 443.3 Problem Formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.3.1 Blockchain-Empowered Ledger System . . . . . . . . . . . . . . . 453.3.2 Selfishness Avoidance . . . . . . . . . . . . . . . . . . . . . . . . 463.3.3 Overall Optimization Problem . . . . . . . . . . . . . . . . . . . . 473.4 Experiment and Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . 483.4.1 Initial Credit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.4.2 Mean Maximum Wait Time . . . . . . . . . . . . . . . . . . . . . . 533.4.3 Mean Task Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . 543.4.4 Time Elapsed . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574 Realizing a Decentralized Computational Resource Sharing System . . . . . 604.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.2 System Modelling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.2.1 Nodes, Accounts, and Balances . . . . . . . . . . . . . . . . . . . . 634.2.2 Transactions and Transaction Confirmations . . . . . . . . . . . . . 644.2.3 Graph of Transactions . . . . . . . . . . . . . . . . . . . . . . . . 654.2.4 Other Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704.3 The Accepted Graph and the Buffered Graph . . . . . . . . . . . . . . . . . 734.3.1 Dimension of the Buffer . . . . . . . . . . . . . . . . . . . . . . . 754.3.2 Maturity and Buffered Graph Advancing . . . . . . . . . . . . . . . 754.3.3 Consensus over the Buffered Graph . . . . . . . . . . . . . . . . . 754.3.4 Parent Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76x4.3.5 Graph Update Algorithm . . . . . . . . . . . . . . . . . . . . . . . 764.3.6 Lazy Nodes and Parasite Chain Attack . . . . . . . . . . . . . . . . 784.4 Experiment and Evaluations . . . . . . . . . . . . . . . . . . . . . . . . . 784.4.1 Buffer Dimension . . . . . . . . . . . . . . . . . . . . . . . . . . . 794.4.2 Comparison with IOTA . . . . . . . . . . . . . . . . . . . . . . . . 814.4.3 Transaction Confirmation Time . . . . . . . . . . . . . . . . . . . . 824.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 845 Conclusions and Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . 865.1 Results and Conclusions of the Research . . . . . . . . . . . . . . . . . . . 865.2 Suggestions for Future Work . . . . . . . . . . . . . . . . . . . . . . . . . 875.2.1 Performance of Heuristic Algorithm for Task Scheduling . . . . . . 875.2.2 Expanding the Local Network . . . . . . . . . . . . . . . . . . . . 885.2.3 Probability Model of Chronological Order of Transactions . . . . . 88Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89xiList of TablesTable 2.1 Default Parameters - Simulation 1 . . . . . . . . . . . . . . . . . . . . . 27Table 3.1 Default Parameters - Simulation 2 . . . . . . . . . . . . . . . . . . . . . 51Table 4.1 Default Parameters - Simulation 3 . . . . . . . . . . . . . . . . . . . . . 79xiiList of FiguresFigure 2.1 Cloud and Fog Computing . . . . . . . . . . . . . . . . . . . . . . . . 15Figure 2.2 Continuous-time Markov chain for the connected-disconnected transi-tion between pi and h j. Let 1/0 represent the state that pi and h j areconnect/disconnected. The transition rates from 0 to 1 and from 1 to 0are given by λi, j and µi, j, respectively . . . . . . . . . . . . . . . . . . 18Figure 2.3 Effect of Number of Requesters on Average Task Execution Time . . . 27Figure 2.4 Effect of Number of Requesters - Normalized Performance . . . . . . . 28Figure 2.5 Effect of Number of Helpers on Average Task Execution Time . . . . . 29Figure 2.6 Effect of Number of Helpers - Normalized Performance . . . . . . . . . 29Figure 2.7 Effect of Mean Maximum Wait Time on Average Task Execution Time 31Figure 2.8 Effect of Mean Maximum Wait Time - Normalized Performance . . . . 31Figure 2.9 Effect of Mean Task Size on Average Task Execution Time . . . . . . . 32Figure 2.10 Effect of Mean Task Size - Normalized Performance . . . . . . . . . . 33Figure 2.11 Effect of Mean Task Size on Average Task Execution Time per Re-quester per Unit Computation . . . . . . . . . . . . . . . . . . . . . . 34Figure 3.1 Typical Blockchain Structure . . . . . . . . . . . . . . . . . . . . . . . 39Figure 3.2 Typical Blocks in our System . . . . . . . . . . . . . . . . . . . . . . . 41Figure 3.3 Task Scheduling in the D2D Network . . . . . . . . . . . . . . . . . . 42xiiiFigure 3.4 Effect of Initial Credit on Average Task Execution Time . . . . . . . . 53Figure 3.5 Effect of Initial Credit on Level of Selfishness . . . . . . . . . . . . . . 53Figure 3.6 Effect of Mean Maximum Wait Time on Average Task Execution Time 55Figure 3.7 Effect of Mean Maximum Wait Time on Level of Selfishness . . . . . . 55Figure 3.8 Effect of Mean Task Size on Average Task Execution Time . . . . . . . 56Figure 3.9 Effect of Mean Task Size on Level of Selfishness . . . . . . . . . . . . 56Figure 3.10 Effect of Ongoing Number of Periods on Average Task Execution Time 58Figure 3.11 Effect of Ongoing Number of Periods on Level of Selfishness . . . . . . 58Figure 4.1 New Transaction Issuance . . . . . . . . . . . . . . . . . . . . . . . . 64Figure 4.2 Graph of Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . 66Figure 4.3 Dimension of Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . 69Figure 4.4 Accepted Graph and Buffered Graph . . . . . . . . . . . . . . . . . . . 74Figure 4.5 Parameter Effect of wmin . . . . . . . . . . . . . . . . . . . . . . . . . 79Figure 4.6 Parameter Effect of hmax . . . . . . . . . . . . . . . . . . . . . . . . . 80Figure 4.7 Comparison with IOTA . . . . . . . . . . . . . . . . . . . . . . . . . . 81Figure 4.8 Effect of Buffer Size on Average Transaction Confirmation Time . . . . 83xivGlossaryAdoP adoptive parentAG accepted graphBG buffered graphBioP biological parentBS base stationCDF cumulative distribution functionsCPU central processing unitCTMC continuous time Markov chainD2D device-to-deviceDAG directed acyclic graphDLT distributed ledger technologyDPoS delegated proof of stakeFC fog computingICO initial coin offeringxvIoT Internet of ThingsMCMC Markov chain Monte CarloMLE maximum likelihood estimationP2P peer-to-peerPoS proof of stakePoW proof of workQoE quality of experienceUTXO unspent transaction outputxviAcknowledgmentsFirst and foremost, I would like to express my deep gratitude to my supervisor, Prof. Vic-tor C.M. Leung, for his patience, encouragement, and priceless advice during my graduatestudy. Over the past years, I am fortunate enough to receive invaluable support and guid-ance from him not only academically but also personally.Besides my supervisor, I would also like to thank the rest of my thesis committee mem-bers, Prof. Chen Feng and Prof. Panos Nasiopoulos, for the time and effort in evaluatingmy work and providing feedback and suggestions.I would like to declare sincere thanks to my co-authors and good friends, Dr. ZehuaWang and Dr. Wei Cai, for their support and advice for my research work and publications.I also want to express appreciation to my colleagues and friends, Xiaotong Wang, ShaotianLiu, Fuchun Ma, Yihao Zhang, among others, for their advice and company towards mygraduate study.Most importantly, I owe my parents a deep debt of gratitude for their unchanged, un-conditional, and unmeasurable love and support.This work was supported by funding from the Natural Sciences and Engineering Re-search Council of Canada.xviiDedicationTo my wife Siying, my son Yulin, and my entire family.xviiiChapter 1IntroductionIn this chapter, background, benefits, and challenges of fog computing (FC) in the device-to-device (D2D) networks are introduced. Motivated by the foreseen need of a satisfactorycomputational resource sharing system in the D2D networks, we strive to overcome somekey challenges towards building such system, including the design of a decentralized ledgersystem. First, we present background and related work in FC and distributed ledger tech-nology (DLT), as well as their applications. Then, we discuss motivation and researchquestions of this thesis, followed by a summary of the main contributions. Finally, theorganization of the thesis is presented.1.1 Background and Related WorkAt present, majority of applications tend to handle their content storage and computationson remote cloud servers that are situated typically very far away from end users. Suchprevalent way of cloud computing has been quite favorable for both service providers andusers because it excludes companies’ need to purchase expensive infrastructures and users’need to update their devices frequently. However, cloud computing is often bonded withhigh price and limited availability. For example, access to WiFi may be quite limited off1home and offices, while more accessible cellular data can be very expensive. With the flour-ishing of smart mobile devices (e.g. smartphones, tablets, wearable devices), developmentof FC has received more and more attention from both industry and academia, aiming atbringing applications closer to end users. The primary advantage of shifting and spreadingthe load of cloud computing to FC is to alleviate current mobile network congestion, whicheventually both enhances quality of experience (QoE) provided to users and reduces servicecost. Other advantages include better availability, lower data transmission delay, etc., as ap-plication data no longer has to travel all the way across continents and then travel back. Toaccomplish the ambitious millisecond-scale latency for computing and communications in5G, it is now agreed widely that relying merely on cloud computing is far too insufficient,which leads to great motivations for a satisfactory computational resource sharing systemin the D2D networks.We face several challenges towards building such a resource sharing system in the D2Dnetworks. First, user mobility substantially increases the uncertainty of computational taskcooperation in a D2D network. For example, an outsourced task may have been handedover and finished by a peer after a period of time, but the computation result fails to besent back in time due to changed connectivity. Moreover, proper incentives or a ledgersystem are needed to enforce fairness among users. Specifically, a selfish user can choosenot to share spare computing power, e.g. by turning off devices, after receiving help frompeers. This sort of selfishness is unfair for other users, and is inevitable without a properledger system. Even though a centralized ledger can be implemented considerably moreeasily, recent upsurge of attention in Bitcoin and other cryptocurrencies reminds peoplearound the world of the importance of DLT. Some disadvantages of a centralized ledgerinclude but not limited to vulnerability to single point of failure, lack of transparency, andrisk of central manipulation. To elaborate on the aforementioned concepts and details ofour system design, we first discuss related work of FC and DLT in the following sections.21.1.1 Fog Computing and the D2D NetworksData and Computation OffloadingTo relieve the burden of wireless cellular networks and the cloud, mobile data and compu-tational traffic can be delivered through other means to the users (e.g., WiFi, D2D commu-nications). This is known as mobile data and computation offloading. Several works haveidentified the benefits of WiFi data and computation offloading [16, 36, 43]. The workin [43] showed that deferring the uploading tasks until WiFi access points are available cansave the energy of smartphones. By jointly considering the power consumption and linkcapacity of wireless network interfaces, Ding et al. in [16] studied the criterion of down-loading data from WiFi as well as the WiFi access point selection problem. Ge et al. in[21] investigated the data and computation offloading with the joint consideration of cumu-lative distribution function based scheduling [20]. With a budget of energy consumptionand monetary cost, the download duration is minimized in [36] by allocating the data traf-fic demand to wireless cellular and WiFi networks. However, mobile data and computationtraffic cannot always be offloaded to WiFi networks since the number of open-accessibleWiFi access points is limited [16].Fog ComputingTherefore, the concept of fog computing [51] is brought up and facilitated to relieve net-work congestion and availability constraints. Fog is an extension of the cloud: it is closerto the users than the cloud, consisting of various user smart devices, computers, and othercomputing units in the ad-hoc. Fog computing refrains users from high carrier data trans-mission cost and cloud computing services cost, and its presence in users’ vicinity alsoallows for low communication latency and high availability, which makes the fog an excel-lent and cost-effective place for data and computation offloading.3D2D OffloadingTo fully exploit the benefits of data and computation offloading, mobile traffic can alsobe delivered via D2D networks. Specifically, mobile devices in close proximity can beconnected via WiFi Direct [2] or Bluetooth in a D2D manner for data and task cooperationbetween users. This is referred to as D2D data and computation offloading. [47] and[17] explored task cooperation of mobile devices in the D2D network and showed thatsignificant execution time and device energy can be saved. Authors of [10] presented aframework for opportunistic storage and processing in the mobile cloud. The work in [5]considered D2D technologies as candidates to deal with most local communications andtime-sensitive computations in near future. A D2D network should make use of Bluetooth,WiFi-Direct, and other protocols to more efficiently provision services to applications suchas video gaming and image processing.Abundance of Spare Resources in the D2D NetworksIt has been shown in [14] that the computational power of our smart mobile devices areidle and wasted for most of the time before these devices become outdated and replacedwith newer models. The work in [19] presents that contemporary smart devices (mostlyquad-core devices) use less than two cores on average in their non-idle states with the con-sideration of simultaneously running applications in the background, not to mention thecomputing power that these devices can provide in their idle states. It is generally true thatbuilding more data centres can provision more computational powers for end users. How-ever, a data centre needs to be built and maintained at a very high cost, which encouragesexploitation of task cooperation possibilities in the D2D networks.4Fog Computing and Internet of ThingsAuthors of [6] investigated into fog computing and its characteristics, roles and poten-tial applications in the area of Internet of Things (IoT). The work considered the fog as aprovider of excellent localization that enables low latency and context awareness. It demon-strated the roles of fog computing in connected vehicles, smart grid, wireless sensors, andactuators networks, and suggests that many future applications require the cooperation ofboth fog localization and cloud globalization. In our work, we extend the idea of fog-cloudcooperation in IoT to a more general application in the D2D networks.Some ApplicationsChi et al. in [11] designed an ad-hoc cloudlet based cooperative cloud gaming system.This tiered system defines the computing power of various mobile smart devices in thead-hoc as ad-hoc mobile cloud; fixed computing units with strong processing capacity thatare deployed in the ad-hoc are defined as an ad-hoc cloudlet. As a result, a three-tiercloud—cloudlet—ad-hoc-mobile-cloud system is formed to coordinate each user’s needfor cooperation in gaming contents and computational tasks in the system based on eachuser’s specific preference on device energy, bandwidth, and response latency. This worktakes the computational power of the fog into consideration, but does not take into accountthe impact of the mobility of these smart devices on task cooperation from a statistical pointof view. Meanwhile, this work assumes that one device may seek for computing resourcefrom only one other device in the D2D network for one computing task. Such assumptionmay limit the scheduling flexibility that may lead to lower QoE for requesters in the system,which should be tackled with dynamic program slicing techniques.Considering mobile nature of smart device users in the ad-hoc, Wang et al. in [49]proposed a metric, expected available duration, based on the mobility and similarities ofusers’ interests in the D2D network. Expected available duration indicates the statistically5determined expected duration of each user’s interested files in the D2D network. With thismetric, this work presents an optimization and performance promotion of a file sharingsystem in the D2D network to reduce the expensive data charge from cellular carriers anddownload more data from neighbours.1.1.2 Blockchain and Distributed Ledger TechnologyPrehistoryResearchers have been working on the implementation of digital cash [9] since 1980s.Before the advent of Bitcoin, academia has established solid foundations in this topic.The blockchain concept, the fundamental form of public ledger, was first introduced fortime-stamped digital documents in 1991 [24]. Later, Merkle tree [37] was incorporatedto the cryptographically secured chain by allowing several documents to be collected intoone block, which improves the system efficiency and reliability [4]. However, the ledgerimplemented with a chain of blocks was still a centralized database, which relies on themaintenance of a trusted third party financial institute.Decentralized Ledger and Double SpendingCentralized systems are criticized for their vulnerabilities, including the single-point-of-failure issue and limited transparency. By contrast, decentralized systems suffer from thedata synchronization issue, which is well summarized in the Byzantine Generals’ Problem[31]. In other words, the participants in the decentralized ledger system need to achieveconsensus, an agreement upon every message broadcasted to each other. For example, acommon Byzantine fault tolerance can be achieved if participating nodes have a majorityagreement on their decisions. While double spending is never an issue in a centralizedsystem, it is a fundamental and critical issue in a decentralized ledger. Thanks to the hash-linking feature of blockchain, each coin in the ledger can be traced back to the first record6when it is created. Therefore, forgery on a non-existing coin is impossible in a publicdecentralized ledgers. However, different from a physical coin, a digital coin can be easilyreplicated by duplicating the data. In this context, it is critical to prevent the dishonestbehaviour that spend one coin more than once. If a dishonest user of the public ledger iscapable to perform Sybil attack, the coins that it double spends will be legalized by themajority of parties, which diminishes user trust as well as the circulation and retention ofthe currency.Proof of Work ConsensusSatoshi Nakamoto borrows the proof of work (PoW) [3] to solve the double spending issuein the first white paper of Bitcoin [39]. The PoW is a mathematical calculation that involvesscanning for a value that when hashed, the hash begins with a number of zero bits, whichis also called mining. Each miner in the ledger network needs to compete with each otherin solving the PoW puzzles. The winner of each competition will have the right to createa block and broadcast it to the peers. With PoW, the cost of double spending is increasedto a very high level, due to the high hardware and computation investment of a particularnetwork participant. On the other hand, the miner who successfully creates a block willreceive coin rewards for its work. This type of PoW consensus mechanism demotivates theintruders, and thus protects the decentralized ledger.Bitcoin [39] is the representative of the classic blockchain systems. As the first de-centralized ledger, it has attracted more than ten thousands miners to establish the largestmarket capitalization among all cryptocurrencies. The most important contribution of Bit-coin is that, it solves the double spending issue to make digital asset unique and valuable.1In fact, the success of Bitcoin opened the blockchain door to the academia, the industry,and even the public.1More precisely, Bitcoin solves the double spending issue with high probability under the assumption ofhonest majority. See Section 11 in the Bitcoin white paper [39].7Other Consensus ModelsThere are lots of other consensus models other than PoW, among which proof of stake(PoS) and delegated proof of stake (DPoS) are quite famous.Different from PoW, network participants in a PoS system do not need to solve themathematical puzzles in order to create a block. Instead, the producer of a block is ran-domly chosen based on the participant’s ownership of stake (i.e., the more stake a partic-ipant has, the more likely it can become a block producer). Under this circumstance, theamount of tokens one node holds becomes the barrier of double spending. In other words,the system intruders will need to hold a significant amount of the coins in circulation toperform double spending. In fact, this is extremely difficult: due to the laws of supply anddemand, the price of tokens in a system will continuously increase when the intruders starttheir purchase, which may punish them economically. More interestingly, once the intrud-ers become major stake holders of a digital currency, they lose their motivation to attack:their attack will disrupt the operation of the currency, which in turn introduces financialdamage to the intruders. One critical issue in PoS is the rational forks by the stakeholders.As we discussed, PoS utilizes stake to replace the PoW computation. However, once ablock producer in a PoS blockchain creates a fork, there is no cost for all stakeholders tofollow the forked sub-chain. Technically, one fork will double the stakeholders’ tokens andtwo forks will triple them. There is nothing to lose for the stakeholders to follow all chainsand receive multiple coins in different sub chains. Too many forks on one blockchain willintroduce chaos and confusions, thereby reducing the value of the network. To this end,only a few cryptocurrencies available in the market are based on PoS, such as Peercoin[30].DPoS is similar to PoS, but network participants delegate their rights of producingblocks to a small group of super nodes. In this case, the stakeholders cannot perform8rational forks, since the votes allocated to the stakeholders are limited in quantity, e.g. pro-portional to the amount of tokens they hold. On the other hand, the elected block producersare supervised by the majority of stakeholders to perform their duties for the incentivesgenerated by creating new blocks. Any malicious behaviours from block producers will bereported and unqualified block producers will be voted out as a consequence. The numberof block producers is subject to different implementations. For example, Asch has 101delegates and EOS has 21 super nodes [25]. Block producers may also serve as gover-nance gateway. Any proposed change on system parameters, such as transaction fee, blocksize, witness pay and block intervals, needs to be approved by majority of block producers.Since the number of block producers in a DPoS model is limited and the voting procedurecan screen out low quality candidates, it is easier for the system to optimize itself in termsof performance. According to this, DPoS features itself with high efficiency and flexibility.However, there are doubts around the mechanism of delegated block producers: opponentscriticize that DPoS is not a decentralized platform, since it is impossible to guarantee thepurity of block producers. The small group of block producers may conspire to maximizetheir own interests. Also, since the block producers will receive rewards, a group candi-dates who did not get elected may create forks on the main chain, which results in multiplechains as well.Of course, there are many other distributed ledger systems that are not permission-less (i.e., not fully decentralized) such as the Hyperledger Fabric [1] and MultiChain [23].These permissioned blockchains and their consensus models remain beyond the scope ofthis thesis as they are after all centralized.Overall, the PoW mechanism is the most mature and PoW-based decentralized ledgersystems are dominating the current blockchain world.91.1.3 DAG-Based Decentralized Ledger SystemsNew Blockchain ParadigmIn addition to the blockchain, a new paradigm is gaining impressive momentum in DLT —the directed acyclic graph (DAG). A DAG is a general term in mathematics, graph theoryin particular, that represents a finite directed graph with no directed cycles. In DLT, someconsensus mechanisms have their transactions and transaction confirmation relationshiprepresented in the form of a DAG. These consensus mechanisms are commonly referred toas DAG-based consensus mechanisms, or simply as “DAG” mechanisms. A DAG is not achain of blocks, and therefore not actually a blockchain, but for simplicity, we regard DAGas part of the blockchain consensus mechanisms, just like PoW and PoS.Superiority over Traditional BlockchainUnlike the traditional blockchain structure that uses a chain of ordered blocks to packageand store transactions, a DAG structure stores transactions in a graph of all individual trans-actions where a directed edge represents a confirmation from one transaction to another.Such a structure refrains the system from the need for miners and mining processes dis-cussed in Section 1.1.2, which contributes to faster transaction rate, zero transaction fees,and higher degree of decentralization. Therefore, it has been widely believed that DAGrepresents the direction for future of blockchain technology. Many companies among thetop pioneers believe that, among many consensus algorithms, those that are DAG-basedare likely the best candidates for applications that need high transaction throughput. Forexample, in a computational resource sharing system in the D2D networks, a lot of micropayments may go on every minute or even every second, which is unrealistic to be backedby most PoW-based systems like Bitcoin.10Existing DAG-Based Blockchain SystemsThe first community to come up with a DAG-based blockchain system is Nxt, who pre-sented the idea to switch from the traditional linked-list structure to a DAG of transactionsstructure [32]. DagCoin was the first publication that suggested storage of all conflict-ing transactions in a DAG and choose one as valid [34]. Byteball presented a consensusmechanism through a main chain of transactions within a DAG, who is also the first tocome up with a witness mechanism in a DAG-based blockchain system [12]. One of theleaders in DAG-based blockchain systems, Nano, is a feeless DAG network where eachparticipant has its own blockchain within the DAG of transactions [33]. IOTA, the topleader in the DAG field, is dedicated for the IoT industry that substantially relies on mas-sive micro-transactions. IOTA claims that, through their governing mechanism, the higherthe new transaction arrival rate, the more secure the system becomes, which naturally fitsthe IoT industry [42]. Both IOTA and Nano once achieved a multi-billion market cap, andwere among the top 20 cryptocurrencies according to Coinmarketcap2. However, manyof the existing DAG-based blockchain projects are not yet decentralized, ironically. Forexample, even IOTA, as the top leader, claims that their system is immature for a full de-centralization, and therefore needs a governing closed-source coordinator that temporarilytakes charge of the security of the system. Overall, the DAG-based mechanisms are rela-tively new and underdeveloped, but are fast-paced in the blockchain field and have drawnenormous attention.1.2 Motivation and Research QuestionsAlthough some of the existing approaches towards local FC services seem promising,no approaches have been proposed to handle D2D computational task outsourcing andscheduling with connectivity-awareness. Depending on various factors such as the task2https://coinmarketcap.com11size and the computing power of a peer, an outsourced task may be completed sooner orlater by that peer. With a connectivity model, one should be able to selectively choose apeer and a properly sized task to be outsourced such that the negative effects due to user mo-bility (e.g. lost connection after task completion) can be significantly reduced. To achievethis, a probability model of user mobility is considered to enable a connectivity-aware taskcooperation system in the D2D networks. Such a system should consider the connectionprobabilities between a user and its peers.Moreover, without a proper ledger system, selfish users may choose to only get helpfrom peers without contributing back. Thus, a ledger system should be considered to en-courage system users to share their spare computational resources in return for future needs.Even though a centralized ledger system can be implemented quite easily, recent upsurge ofattention in decentralized cryptocurrencies, with their numerous applications, reminds peo-ple around the world of the importance of DLT. Some disadvantages of a centralized ledgerinclude but not limited to vulnerability to single point of failure, lack of transparency, andrisk of central manipulation. Consequently, a decentralized ledger system is considered toenforce fairness in our resource sharing system.Nevertheless, a proper decentralized ledger system should be designed not only to en-force fairness among system users, but also to enforce it in an effective manner. Amongmany candidates in the field of DLT, DAG-based decentralized systems are widely be-lieved to represent the direction for the future due to its high efficiency in terms of powerconsumption, transaction throughput, etc. Therefore, on top of the task cooperation sys-tem, an efficient DAG-based decentralized ledger system is designed and enforced. Toput it together, we are interested in designing a proper scheduling scheme for connectivity-aware task outsourcing, and an efficient DAG-based decentralized ledger system in order toconstruct an effective and fair computational resource sharing system in the D2D networks.121.3 ContributionsIn this thesis, we• proposed a novel connectivity-aware cooperative task scheduling scheme to help auser to outsource appropriate amount of computational tasks to appropriate users atappropriate time,• presented how a decentralized blockchain-based ledger system can substantially re-duce selfishness in the system by sacrificing only minor amount of task executiontime,• and designed a DAG-based decentralized ledger system that allows our computa-tional resource sharing system to support a high transaction throughput.1.4 Thesis OrganizationIn Chapter 2, we present how mobility and connectivity considerations can lead to a moreeffective computational resource sharing system in the D2D networks by adopting ourscheduling paradigm. In Chapter 3, we present how a traditional PoW based decentralizedledger system can greatly reduce selfishness in the system by sacrificing only little amountof average task execution time. In Chapter 4, a novel DAG-based decentralized ledger sys-tem is designed to realize our resource sharing system with high transaction throughput.Finally in Chapter 5, conclusion and future work suggestions are drawn.13Chapter 2Connectivity-Aware Task Outsourcingand Scheduling2.1 OverviewAdvances in computing technology are transforming the way people execute computationaltasks for daily applications like stock trading [48], gaming [7], etc. Usage of traditionaldesktop computers for large computation works has been expanded to various ways ofcomputing such as cloud computing. For example, cloud gaming platforms PlayStationNow [41] and GameFly [18] execute most gaming computational tasks on the cloud, whichfrees gamers from having to update their computing devices frequently. Stock market in-vestors are now able to manipulate stock trading on their mobile devices by offloading mostcomputational tasks to the cloud [48]. In recent years, with the explosion of smart mobiledevices and their capacities in terms of computing power, storage, data transmission effi-ciency, etc., the concept of fog computing [51] is facilitated to overcome high data cost andmobility constraints.As illustrated in Figure 2.1, fog is an extension of the cloud: fog is lower and closer14Figure 2.1: Cloud and Fog Computingto users than the cloud; it consists of various user smart devices, computers and othercomputing units in the ad-hoc. Although it is widely adapted contemporarily to offloadcomputational tasks to the cloud as the fog does not have as high density (calculation andstorage capacities), fog computing prevents high carrier data transmission cost and cloudcomputing service cost, and its presence in users’ vicinity allows for short communicationlatency. Intermittent access to cellular data and non-seamless wireless coverage in themobile environments are also discouraging factors for users to completely rely on the cloud.Faster and more responsive task cooperation and offloading in the ad-hoc becomes evenmore necessary in extreme situations like earthquake response.The work in [14] shows that despite increasing usage of mobile devices in our dailylives, most of the computational power of these smart devices are still in the idle state andwasted, e.g. only email notification listeners and other low consumption applications run at15the background for most of the time. If we can take advantage of computational power ofthese idle devices together with their storage and data layover abilities, cost-effective taskcooperation in the D2D networks is highly feasible. Such task cooperation and offload-ing context was first presented in Serendipity [47], a system that allows a mobile initiatorto utilize computational resources available in other mobile systems in its surrounding toaccelerate computing and save energy, whose performance is further analyzed in [17] tosee significant potential gain in both execution time and device energy. The authors of[46] proposed a mobile application that enables cooperation of computationally intensiveapplications by making use of computational powers of mobile devices in nearby cloudlet.While many previous works tried to exploit how idle computational power can be ef-fectively utilized in the D2D networks, mobility aspects of users, especially the task coop-eration scheduling in the mobile environments, still remain open issues. In this chapter, wewill propose a task outsourcing and scheduling scheme that is probabilistically based onthe mobility of smart mobile device users in a D2D network.2.2 System ModellingIn this section, we will first introduce the basic system settings, and then present the con-nectivity model, dynamic program slicing and task cooperation scheduling backgroundsfor our system.2.2.1 Basic System SettingsWe divide the set of all system members with a smart device in the D2D network into twomember sets, namely, requester set P and helper set H. There are p requesters in P andh helpers in H, where p ≥ 1 and h ≥ 1. Each requester is denoted as pi ∈ P and eachhelper is denoted as h j ∈ H, where i ∈ {1,2, ..., p}, j ∈ {1,2, ...,h}. The smart device of arequester pi or helper h j is subject to a D2D communication range rpi or rhj , respectively,16above which D2D direct link connection is not possible. We use cpi or chj to denote theavailable computational power of a requester or helper, indicating how fast or how muchcomputation the smart device is able to handle per second for our cooperative scheme.Typically, this type of computational power is represented by how many clock cycles thedevice can run per second, 2.6 GHz for example. At any moment τ ≥ 0, each requesterpi initializes a task of complexity Ti,τ in clock cycles (indicating how many clock cyclesneeds to be run to get the result of the task) with its maximum wait time ti,τ in seconds(indicating the maximum time pi will wait for the result until he/she has to do the assigneduncompleted task slices by himself/herself).2.2.2 Connectivity ModelAssuming the connection between a requester pi and a helper h j is symmetric, we denotethe random variable Bi, j(τ) = 1 (or Bi, j(τ) = 0) to represent that pi and h j are connected(or disconnected) at τ ≥ 0. Moreover, let random variable S1i, j denote the sojourn time thatpi and h j are in the connected state, and S0i, j denote that in the disconnected state. Weconsider both S1i, j and S0i, j follow the exponential distribution with parameters µi, j and λi, j,respectively. Therefore, we have the cumulative distribution functions (CDF) of S1i, j andS0i, j given byPr(S1i, j ≤ τ) = 1− eµi, jτ , (2.1)andPr(S0i, j ≤ τ) = 1− eλi, jτ . (2.2)We represent the continuous time Markov chain (CTMC) model with two states illustratedin Figure 2.2, and let Pi, j(τ) denote the 2× 2 matrix with entries pxyi, j(τ) = Pr(Bi, j(τ) =y|Bi, j(0) = x), where x,y ∈ {0,1}. Referring to [40], we have the solution of Pi, j(τ) given17byPi, j(τ) = λi, jψ + µi, jψ κ µi, jψ − µi, jψ κλi, jψ −λi, jψ κµi, jψ +λi, jψ κ , (2.3)where κ = e−(µi, j+λi, j)τ , and ψ = µi, j+λi, j.Figure 2.2: Continuous-time Markov chain for the connected-disconnected transitionbetween pi and h j. Let 1/0 represent the state that pi and h j are connect/discon-nected. The transition rates from 0 to 1 and from 1 to 0 are given by λi, j andµi, j, respectivelyThe parameters µi, j and λi, j used in Equation 2.3 for pi and h j can be obtained by maxi-mum likelihood estimation (MLE) on each of them. Specifically, without loss of generality,consider pi and h j were disconnected initially and the connectivity between pi and h j haschanged m times before the current time τ . Therefore, pi and h j have recorded a vectorof time ~τi, j = (τ1, ...,τm) ∈ Rm+, where each element τki, j < τ(k = 1, ...,m) represents thetime when the connectivity between pi and h j changed. Assume pi and h j are currentlyconnected (then m must be an odd number and the case that pi and h j are currently dis-connected can be analyzed via following approach similarly), the µi, j and λi, j estimated byMLE up to current time τ are given by18µˆ ti, j =m−12∑m−12k=1(t2ki, j− t2k−1i, j ), (2.4)andλˆ ti, j =m−12∑m−12k=1(t2k+1i, j − t2ki, j). (2.5)Because the connections between pi and h j are assumed symmetric, same results are ob-tained on pi and h j.For the people study or work together, ~τi, j is kept being recorded by both pi and h j asthe system time increases. According to (4) and (5), µˆ ti, j and λˆti, j will converge. We denoteµˆi, j = limt→∞ µˆ ti, j and λˆi, j = limt→∞ λˆti, j, which are the MLE of µˆi, j and λˆi, j, respectively.Given the connection status Bi, j(τ) between pi and h j at time τ , the probability thatthey are connected at future time τ ′ ≥ τ is given byPr(Bi, j(τ ′) = 1|Bi, j(τ))=λi, j−λi, je−(λi, j+µi, j)(t′−t)λi, j+µi, j, Bi, j(τ) = 0,λi, j+µi, je−(λi, j+µi, j)(t′−t)λi, j+µi, j, Bi, j(τ) = 1.(2.6)2.2.3 Dynamic Program SlicingIn general, computational tasks cannot be arbitrarily sliced into different parts. However,many dynamic program slicing techniques are facilitating our need for distribution of tasks[22]. For example, MapReduce [15] allows Google to slice and run an average of onehundred thousand MapReduce jobs every day from 2004-2008. Without the availabilityof dynamic program slicing, a large load of task may not be sent back to the requester in19a timely manner, and increases the risk of helper being out of the device communicationrange of the requester on completion of the task execution. Even though it is unrealistic topartition a computational task into pieces with an arbitrary size, it is generally feasible toslice a reasonably-sized task into many pieces making use of a program slicing techniquelike that proposed in [22] or [15]. For simplicity, we adopt the assumption that a compu-tation piece of an exact portion, e.g. 33%, can be sliced out from the original task in oursystem.2.2.4 Task Cooperation SchedulingIn our system, we assume that a computing unit, which we refer to as a supernode, withenough capacity to perform task cooperation scheduling for all devices is available at thecellular base station covering the D2D network. At the beginning of each task period, thesupernode collects task and connectivity information sent wirelessly from the devices andcomputes the task scheduling for requesters and helpers in the D2D network based on prob-ability of connection among them according to (2.6). Note that the task and connectivityinformation sent to the supernode is very limited in size and transmission time, which areassumed to be negligible for simplicity. Each task period is divided into discrete time slotsfor scheduling to ensure accuracy, latency, and to lower the chance of losing computationresults due to changes in connectivity. This computation will be based on an effectivelight-weight algorithm elaborated in Section Problem FormulationAs mentioned in the previous section, we assume that a supernode with enough capacity ispresent at the base station covering the D2D network of our interest. At the beginning ofeach task period, the supernode will, with the knowledge of all devices and tasks in the D2Dnetwork, calculate the probability distribution of the connectivities between devices, and20assign computational tasks to each helper or requester device accordingly. Connectivity-awareness, computational task assignment, response delay optimization, and the overalloptimization problem are mathematically formulated in this section.2.3.1 Connectivity AwarenessTo analyze the connectivity between requesters and helpers for more accurate and cost-effective computation assignment, we first define a p×(h+1) probability matrix Rt at eachtime slot t ∈ {0,1, ..., T∆t }. For a given t, the element Ri, j,t is the probability of connectionbetween pi and h j if j ∈ {1,2, ...,h}, and Ri,(h+1),t indicating the probability of connectionbetween pi and herself/himself. Obviously, Ri,(h+1),t = 1 ∀ i, t. At the start of each taskperiod, i.e. t = 0, we randomly generate Ri, j,0 ∀ i ∈ {1,2, ..., p}, j ∈ {1,2, ...,h} based onthe pre-defined initial connection probability. Thereafter, according to Equation (2.6), wegenerate Ri, j,t ∀t ∈ {1,2, ..., T∆t } for each pi-h j pair.At any given time slot t ∈ {1,2, ..., T∆t }, we define a p-element vector~It with its elementIi,t representing the amount of self-computing computational task assigned to pi, and ap×h matrix Jt with element Ji, j,t representing the amount of assisting computational taskassigned to h j for pi. By concatenating Ji, j,t and Ii,t , we get a p× (h+ 1) computationassignment matrix Mt = [Ji, j,t Ii,t ] at time slot t. Joining all Mt where t ∈ {1,2, ..., T∆t }, weget a p×(h+1)× T∆t 3-dimensional system computation assignment matrix, M, containingthe computation assignment in a task period τ ∈ [0,T ]. Consequently, Mi, j,t where j ∈{1,2, ...,h} is the amount of computational task assigned to h j for pi and Mi,h+1,t is theamount of self-computing computational task assigned to pi at time slot τ = t.Note that the element-wise product between R and M,Mexp =MR, (2.7)21is the matrix indicating the expected amount of computational task done and result sentback to requesters. For example, Mexpi, j,t = Mi, j,t ·Ri, j,t is the expected amount of assistingtask done by h j and sent back to p j at time slot τ = t.2.3.2 Computation Assignment and Maximum Wait TimeAt the start of each task period, all requesters will specify to the supernode at the basestation the amount of computation, in clock cycles, required for the coming task period. Werepresent these tasks with a p-element vector~γ with γi corresponding to the total amount oftask required by pi. Meanwhile, for an ensured QoE, pi is also subject to a maximum waittime in each task period for the result of the computational task. We use another p-elementvector ~φ with φi corresponding to the maximum wait time for pi in seconds. Apparently,φi ≤ T, ∀i. Therefore, the computation assignment needs to ensure that a task is expectedto be completed before the maximum wait time for all requesters, that is:γi ≤φi/t∑t=1(h+1)∑j=1Mexpi, j,t , ∀i ∈ {1,2, ..., p} (2.8)2.3.3 Computational Capacity of Mobile DevicesEach mobile device is subject to a computation capacity denoted as cpi for pi’s mobiledevice and chj for h j’s mobile device where i ∈ {1,2, ..., p}, j ∈ {1,2, ...,h}. When talk-ing about computation capacity of a device, one typically will refer to the central pro-cessing unit (CPU) of it. CPU processing capacity is typically referred to in terms ofMegahertz (MHz) or Gigahertz (GHz). Professionals talk about clock speed, which is thestandard ability of the CPU to cycle through its operations over time. Therefore, a 1 GHzCPU is able to tick its clock around 1 billion times per second, which in turn can per-form more complicated computational tasks. Without loss of generality, we regulate these22computational power values in clock cycles to a scale of 0 to 100, i.e. 0 ≤ cpi ≤ 100 and0≤ chj ≤ 100 ∀ i, j, for simplicity. Each entry of the computation assignment matrix, Mi, j,t ,refers to the number of clock cycles required to perform the corresponding task section.For example, M3,4,0 = 1000 means that at t = 0, h4 is assigned to help p3 for a 1000 clockcycles worth of computational task. If ch4 = 50Hz, then it takes h4M3,4,0chj= 100050Hz = 20s toperform the task. Therefore, each device is subject to an amount of computational task inclock cycles at each time slot as a higher limit, that is:p∑i=1Mi, j,t ≤ chj , ∀ j ∈ {1,2, ...,h}, t ∈ {1,2, ...,T∆t} (2.9)for all helper devices, andMi,h+1,t ≤ cpi , ∀i ∈ {1,2, ..., p}, t ∈ {1,2, ...,T∆t} (2.10)for all requester devices as the (h+1)th column of the computation assignment matrix arerepresenting the amount of self-computing tasks.2.3.4 Response Delay OptimizationIn our work, we emphasize the importance of low task execution time towards a requester’sQoE. In each task period, there is n= T∆t time slots and we define the expected completiontime, texpi for each requester pi as follows:texpi = argmintt∑τ=1(h+1)∑j=1Mexpi, j,t ≥ γi, (2.11)where i ∈ {1,2, ..., p}, j ∈ {1,2, ...,h}, t ∈ {1,2, ..., T∆t }.23Algorithm 1: The algorithm to schedule task cooperation for i ∈ U uses to obtainK tj,i from user j ∈U \{i}.1 Initialize ~φ .2 [A,b,Aeq,beq] := get linprog parameter(~φ)3 [x, f easible] := linprog(~0,A,b,Aeq,beq,~0)4 if feasible then5 C := {1,2, ..., p}6 Loop7 while C 6= /0 do8 for i ∈ C do9 temp := φi.10 φi := bφi2 c.11 [A,b,Aeq,beq] := get linprog parameter(~φ).12 [x, f easible] := linprog(~0,A,b,Aeq,beq,~0).13 if !feasible then14 φi := temp.15 C := C \{i}.2.3.5 Overall Optimization ProblemFinally, we derive the overall optimization problem as follows:Minimize:p∑i=1texpiSubject to: (2.7−2.11).(2.12)Calculation of the optimal computation assignment matrix M is similar to the famousknapsack problem that is NP-hard [29]. Here, the computational power of helper devicesare like knapsacks with different sizes, and the computational tasks from requesters are likeitems with different sizes. Solving for the optimal solution for the task scheduling resem-bles solving for an optimal solution for knapsack problem: it is NP-hard. For effectiveness,especially considering the trend of increasingly massive number of smart mobile devicesin D2D networks, we proposed a light-weight heuristic algorithm to efficiently find the24sub-optimal solution for the computation assignment matrix M illustrated in Algorithm 1.Note that we make substantial use of the linprog function in MATLAB for calculating thecomputation assignment matrix M by transforming M element-wise into a one-dimensionalunknown vector~x with p · (h+1) · T∆t entries from elements in M. According to linprog, A,b in Algorithm 1 represent the inequality constrains for~x, and Aeq, beq represent the equal-ity constrains for~x. There is no upper bound for~x, and the lower limit for elements of~x is0. The maximum wait time of a requester is the longest time the requester can wait beforeshe/he needs to compute the task result herself/himself. However, it is possible that the taskcan be completed much sooner than the maximum wait time. Each iteration of Algorithm1 tries to find lower feasible task assignment solutions by halving (up to an integer value) arandomly-selected requester’s maximum wait time. Since the duration of each task periodis limited, the maximum wait time is up to the length of a task period. Therefore, the com-plexity of Algorithm 1 is subject to ln(p) ·O(linprog) where p is the number of requestersat the task period and O(linprog) represents the complexity of MATLAB’s linprog func-tion [35]. Unfortunately, MATLAB claims improvement on efficiency of linprog over time,but releases no detail about the complexity. Yang in [50] claims that his algorithm on topof linprog may achieve polynomial complexity with the best known complexity bound onlinear programming problems.2.4 Experiment and EvaluationsIn a D2D network, a variety of factors may affect the performance of our cooperativesystem and proposed algorithm. In this section, we will examine the following effects:• Effect of number of requesters: we fix the number of helpers and vary the number ofrequesters to see the performance change of our system.• Effect of number of helpers: we fix the number of requesters and vary the number of25helpers to see the performance change of our system.• Effect of mean maximum wait time: we vary the mean maximum wait time duringthe random generation to see how the performance will be affected.• Effect of mean task size: we vary the mean task size of each requester in a task periodduring the random generation to see how the performance will be affected.In our simulation, we compare our proposed cooperative task scheduling scheme to thebasic no-cooperation case and a greedy case:• Basic non-cooperation: no D2D cooperation is performed during the simulation, thetask execution is done solely on each requester device itself.• Greedy D2D task cooperation: without connectivity-awareness, each helper devicewill equally contribute its available computing power to all connecting requestersat the beginning of a task period. For example, helper h5 will assignch53 computingpower to each of p1, p3, p4 for the current task period if and only if p1, p3, p4 arethe only requesters in connection with h5 at time τ = 0.• Connectivity-aware task scheduling: at the start of each task period, the supernode atthe base station will perform task scheduling calculation according to Algorithm 1.To validate the performance of our proposed system, we set up the following experi-ment. Default simulation parameters are illustrated in Table 2.1, where uniform distributionbetween two values a, b is denoted as U [a,b].2.4.1 Number of RequestersWhen there is a fixed number of helpers in the D2D network, the number of requestersbecomes an important factor affecting our system. Imagine there are much more requesters26Table 2.1: Default Parameters - Simulation 1Number of requesters p 6Number of helpers h 10Tasks period T 60sSize of time slots ∆t 5sMaximum computation capacity cmax 100Minimum computation capacity cmin 30Computation capacity cpi or chj U [cmin,cmax]Mean task size per second σ 50 (U [25,75])Mean maximum wait time 40s (U [20s,60s])λi, j U [10−5,10−3]µi, j U [10−3,10−2]Initial connection probability at τ = 0 50%in the network than helpers, then each helper may be assigned to assist many requesters atthe same task period. On contrast, if there are only a few requesters in the system, manyhelpers may assist only one requester at the same time, which greatly reduces the averagetask execution time for the requesters.2 4 6 8 10 12 14 16 18 20Number of Players01020304050Average Run Time per Player (s)Comparison of AlgorithmsNon-cooperativeGreedyHeuristicFigure 2.3: Effect of Number of Requesters on Average Task Execution TimeAs illustrated in Figure 2.3, the average task execution time per requester is only 25%272 4 6 8 10 12 14 16 18 20Number of Players00.511.522.533.54Normalized Performance (Speed)Comparison of AlgorithmsHeuristicGreedyNon-cooperativeFigure 2.4: Effect of Number of Requesters - Normalized Performanceof that in the non-cooperative case, and 40% of that in the greedy case. The increasein number of requesters degrades our system in that the average task execution time forrequesters is increased. However, as shown in Figure 2.4, the effect of increase in numberof requesters also itself degrades and levels off when the number of requesters is around 14(note that the number of helpers here is 10). In comparison, number of requesters seems tohave limited effects on non-cooperative and greedy cases. In the greedy case, the averagetask execution time changed from 34s when p= 2 to 40s when p= 20. Normalized speedof the greedy D2D cooperation is always around 50% better than non-cooperative case,compared to 75% to 400% faster for our heuristic algorithm.2.4.2 Number of HelpersSimilarly, when there is a fixed number of requesters in the D2D network, the number ofhelpers in turn becomes an important factor affecting our system. The effect of increase innumber of helpers in the system is shown in Figure 2.5 and Figure 2.6.As shown, the increase in helper upgrades our system in that the average task execution280 5 10 15 20 25 30Number of Helpers01020304050Average Run Time per Player (s)Comparison of AlgorithmsNon-cooperativeGreedyHeuristicFigure 2.5: Effect of Number of Helpers on Average Task Execution Time0 5 10 15 20 25 30Number of Helpers00.511.522.533.544.5Normalized Performance (Speed)Comparison of AlgorithmsHeuristicGreedyNon-cooperativeFigure 2.6: Effect of Number of Helpers - Normalized Performancetime over all requesters is decreased for both heuristic and greedy algorithms. Figure 2.5shows that initially, when h = 2, our system with scheduling based on the heuristic algo-rithm takes only 58% and 68% of the average task execution time for the non-cooperative29and greedy cases respectively. While the increase in number of helpers decreases the aver-age execution time for the greedy algorithm, the decreasing effect start to fade out when thenumber of helpers increases beyond h = 10. However, the average execution time for ourconnectivity-aware task scheduling base on the heuristic algorithm continue to remainingdecreasing all the way, reaching to only around 20% of the non-cooperative case. Figure2.6 illustrates the normalized performance of the greedy and heuristic algorithm with re-spect to the non-cooperative case. Though the performance of the greedy task cooperationremains level beyond h = 10, cooperative task execution speed of our connectivity-awarescheduling continue to enhance as the number of helpers grows up with a close-to-linearrelationship. Note that the average execution speed for the heuristically calculated taskscheduling for the 6 requesters increased by a factor of 200% when we increase the num-ber of helpers from h = 10 (1.67 times more than number of requesters) to h = 20 (3.33times more than number of requesters).2.4.3 Mean Maximum Wait TimeDuring a task cooperation in the D2D network, the requester typically wants the task to bedone in a timely manner. For example, if a requester wishes to perform a neural networkbased stock index prediction task [8] that predicts the price of a stock in 30 seconds, thisrequester will want to get the computation result within 30 seconds (could be 20 seconds,25 seconds, etc. depending on the specific application logic and handling behind).As illustrated in Figure 2.7, the performance of the greedy cooperation algorithm andnon-cooperative task execution is not noticeably affected the maximum wait time of re-questers. In contrast, average task execution time is around 13 that of the non-cooperativecase and around 23 that of the greedy case when the mean maximum wait time is beyond20 seconds. It is worth noticing that the average task execution time is lowered to approx-imately only 10% that of the non-cooperative case when mean maximum wait time is re-300 10 20 30 40 50 60Maximum Wait Time (s)01020304050Average Run Time per Player (s)Comparison of AlgorithmsNon-cooperativeGreedyHeuristicFigure 2.7: Effect of Mean Maximum Wait Time on Average Task Execution Time0 10 20 30 40 50 60Maximum Wait Time (s)0123456789Normalized Performance (Speed)Comparison of AlgorithmsHeuristicGreedyNon-cooperativeFigure 2.8: Effect of Mean Maximum Wait Time - Normalized Performanceduced to 5 seconds. The reason behind is that the number of feasible solutions decreases asthe mean maximum wait time decreases. When the mean maximum wait time of requestersis very short, e.g. 5 seconds in Figure 2.8, the number of feasible solutions becomes very31small, and any feasible solution becomes very close to the optimal solution. Therefore,shorter mean maximum wait time generally allows our proposed heuristic algorithm to findout better scheduling for task cooperation in the D2D network.2.4.4 Mean Task SizeFinally, we investigated into the effect of change in mean task size to our proposed system.The generation of task sizes in a period T is a uniform distributionU [0.5σT,1.5σT ]. Notethat it is possible that the task size for a requester within a period is over the computingcapacity of the requester device itself. Therefore, a D2D cooperation is required if the taskneeds to be done within the maximum wait time.10 20 30 40 50 60 70 80 90 100Normalized Mean Task Size0102030405060708090100Average Run Time per Player (s)Comparison of AlgorithmsNon-cooperativeGreedyHeuristicFigure 2.9: Effect of Mean Task Size on Average Task Execution TimeFrom Figure 2.9, we can see that the average task execution time is approximately pro-portional to the mean task size for all three compared cases. In other words, a requesterwho wishes to execute a more complex computing task, e.g. neural network based stockindex prediction, that requires higher amount of computation will need more time to co-operatively execute the tasks in the D2D network than other requesters who only need to3210 20 30 40 50 60 70 80 90 100Normalized Mean Task Size00.511.522.5Normalized Performance (Speed)Comparison of AlgorithmsHeuristicGreedyNon-cooperativeFigure 2.10: Effect of Mean Task Size - Normalized Performanceperform simple computational tasks, e.g. simple image processing to shrink the file sizeof an image, that require much less amount of computation. Note that the average taskexecution time for non-cooperative case is beyond the duration of a task period (60s) whenthe mean task size is beyond 50, meaning that these tasks are typically not completed bytheir maximum wait time. Average task execution time for the greedy cooperation case isbetter but is still beyond the duration of a task period when mean task size grow beyond80. Average task execution time for our heuristic case is increasing at a much slower pathand remains well under 40s even when the mean task size in increased to 100.Normalized performance in Figure 2.10 illustrates that the normalized average execu-tion speed of our heuristically scheduled task cooperation experienced a 25% performanceincrease when the mean task size is increased from 10 to 100. In comparison, the normal-ized execution speed of the greedy case experienced a constant decrease when the meantask size increase from 30 beyond, from a 200% faster speed than the non-cooperative caseto only 30%. The normalized execution speed of the heuristic algorithm based scheduling,33however, is 300% faster than the non-cooperative case when the mean task size is 100.10 20 30 40 50 60 70 80 90 100Normalized Mean Task Size00. Run Time per Player per Unit Computation (s)Comparison of AlgorithmsNon-cooperativeGreedyHeuristicFigure 2.11: Effect of Mean Task Size on Average Task Execution Time per Re-quester per Unit ComputationIf we look at the average task execution time per unit of computation, as illustratedin Figure 2.11, we can see that as the mean task size increases, the average execution timerequired per unit of computation actually decreases a little and remains stable overall in ourproposed heuristic algorithm based task scheduling. This is an indication that, in terms ofexecution time per unit of computation, the performance of our cooperative task schedulingis quite stable.2.5 SummaryIn this chapter, we presented a connectivity-aware mobile task outsourcing and schedulingparadigm in the D2D networks. A supernode at the base station, with knowledge of usermobility and thus probability model of device connectivity, will perform task schedulingto reduce average task execution time for requesters in the network to enhance user QoE.Simulation results based on realistically examined mobility model show that our system34substantially reduces average task execution time for requesters in the D2D network. Whenmean maximum wait time is as low as 5 seconds, the average task execution time perrequester is only around 10% that of the non-cooperative case. The performance of oursystem also is approximately directly proportional to the number of helper devices in theD2D network, which is increasingly desirable as the number of smart devices is rapidlyincreasing for potential applications in the area of IoT.35Chapter 3Decentralized Ledger System andSelfishness Avoidance3.1 OverviewIn the previous chapter, we demonstrated how connectivity can be incorporated into co-operative task scheduling in the D2D networks to effectively lower average task executiontime. However, it may be doubted whether this type of task scheduling scheme, thougheffective, presents fairness among users. In other words, it can be unfair for users whocontribute lots of computational resource while receiving little when in need. Such kind ofselfishness is inevitable without a proper ledger system. Even though a centralized ledgersystem can be implemented more easily, recent rage in Bitcoin and other cryptocurrenciesreminds people of its disadvantages (e.g. vulnerability to single point of failure and risk ofcentral manipulation) and the importance of DLT.In the past couple of years, the blockchain and DLT have attracted a great deal of atten-tion in both the academia and the capital market. It is widely believed that the blockchainand DLT will reshape the future in many areas including banking, supply chain manage-36ment, cybersecurity, and government services, etc. In general, the blockchain or a dis-tributed ledger system is a kind of decentralized database with no system administrator.Thus, the database cannot be tampered upon individual’s wish. Instead, a number of dis-tributed peers and system members maintain the peer-to-peer (P2P) network and need toreach a consensus before saving any data to the database. Besides the decentralized man-agement, another difference of a distributed ledger system from the traditional databasemanagement system is that the history of the records cannot be deleted or modified. Forinstance, if a bank uses a decentralized ledger system to maintain customer credits andbalances, all the detailed transactions will be permanently saved in the blockchain and de-centralized ledger so that any person should not be able to remove or tamper the historicalrecords. Such a feature substantially enhances transparency and prevents central authorityfrom manipulating the database, which boosts user confidence. In addition, the P2P natureconsiderably reduces the chance of a single point of failure, as multiple copies of the ledgerare available in the system.As explained in Section 1.1.2, among many existing consensus mechanisms for a de-centralized ledger system, PoW is the most mature. In this chapter, we are interested in in-corporating a PoW-based blockchain ledger system to enforce fairness among users whilenot affecting much on effectiveness of task cooperation.3.2 System DesignThe system consists of two major parts: the cooperative task scheduling to enhance taskexecution effectiveness among users (presented in Chapter 2) and a PoW-based blockchainledger system to provide fairness and other benefits (e.g. anonymity) to users. In thissection, we present some basics and design details of our blockchain ledger system, andthe overall working process of the computational resource sharing system.373.2.1 Blockchain Ledger BasicsAmong many blockchain consensus mechanisms such as PoS and DPoS, PoW is knownto be the most developed, secured, and decentralized, which naturally becomes the keycornerstone of our blockchain ledger system. There are many reasons that a PoW-basedblockchain ledger system is suitable to our D2D resource sharing system. First, a PoW-based blockchain needs to be maintained by mining (to be explained below), which canbe performed by any of our system nodes. Second, the blockchain is available to all users,which is transparent and immutable so that system users are in charge of their own accountsand transactions. Third, the transactions on the blockchain are anonymized, which providesuser privacy, just to name a few. The following are some key basics related to our PoW-based blockchain ledger system:• Blockchain: Blockchain is a distributed data structure consisting of a chain of blocks.Blockchain works as a distributed database or a public ledger that keeps records ofall transactions in the blockchain network. The transactions are time-stamped andlisted into blocks where each block is identified by a unique cryptographic hash.Each block links to it previous block by referencing the hash value of the previousblock, forming a chain of blocks and thus called a blockchain. A blockchain ismaintained by a network of nodes, and every node records the same transactions.The blockchain is publicly accessible among the nodes in the blockchain network.Figure 3.1 illustrates the structure of a blockchain.• Blocks: The transactions in a blockchain network are bundled into blocks. Theseblocks are executed and maintained by all nodes in the network. A block consists ofits hash, the hash of its previous block, a nonce that is used to avoid malicious nodesfrom flooding the network, a transaction list and a timestamp. In order to save storagespace, the transaction list is typically stored in a Merkel root [38] format in each38Figure 3.1: Typical Blockchain Structureblock. Only one of the conflicting transactions (e.g., transactions trying to doublespend) will be taken as part of the block. The blocks are added to the blockchain atregular intervals by miners.• Transactions: A transaction is between two nodes in the blockchain network. Eachtransaction mainly includes the addresses of the sender and recipient, as well as atransaction value. In a valid transaction, the transaction value is transferred from thesender to the recipient. All transactions are signed by the sender’s private key as adigital signature. Transactions are chosen and included in the blocks in the miningprocess. All transactions on a blockchain can be accessed by all participants in thenetwork.• Mining: Transactions in a blockchain network are verified in a process called mining.Incentives, in the form of credits or cryptocurrencies, are awarded to participatingnodes for performing the mining operations. Nodes participating in mining are calledminers. A miner typically is required to select new transactions from a transactionpool, include them in a candidate new block and perform a mathematical computationto determine an appropriate nonce for the new block. This process of performing the39mathematical computation is referred to as “proof of work” [26], which is mainlyused to prevent malicious nodes from arbitrarily adding new blocks to the blockchainor “flooding” the network. The first miner to come up with a valid nonce for a newblock accepted by majority of the network gets the block reward. Miners produceblocks that are then verified by other miners in the network for validity. Once a newwinning block is selected, all other miners update to that new block. The longer theblockchain becomes, the harder for a malicious node to tamper with it. Therefore,mining is typically the key to keep data safety in blockchain applications.3.2.2 Design SpecificsTransaction PoolAfter a task cooperation is performed between a requester and a helper, both of them willhave an identical transaction generated. Each of them will store this transaction into its owntransaction pool on the device and also broadcast it to nearby peers. Each peer will then alsostore the transaction into its own transaction pool upon reception of the new transaction.Note that the supernode has the information of all transactions in the D2D network, so thesupernode holds the publicly accessible full transaction pool for all users in the network.The storage space of these transactions in a transaction pool is negligible.Unspent Transaction Output ModelFigure 3.2 is a typical portion of the blockchain in our system. Each block is identifiedwith a 256-bit unique hash value and links to its previous block. Each block containstransactions (also identified with a 256-bit unique hash value) that contain informationabout the cooperative work in the D2D network. For example, Transaction 1 in the leftblock is recording that User 1 paid 2000 credits to User 2 for receiving the correspondingamount of helper work from User 2. As a safety feature, each transaction needs to point40to the source of the income of the credit, as a proof of enough credit. This safety featureis called an unspent transaction output (UTXO) model and is adopted in Bitcoin and manyother blockchain systems. For instance, Transactions 1 and 2 at the right block both pointto Transaction 1 in the left block since this is an indication that User 2 does have enoughcredit to pay the total of 1600 credits in the right block. Similarly, Transaction 3 at theright block also points to Transaction 2 in the left block, indicating that User 4 has enoughcredit. Note that for demonstration purposes, users are labelled asU1,U2, etc., in the figure.In fact, these users are actually represented as 256-bit unique digital addresses to provideanonymity. Users are also able to change their addresses to further enhance anonymity andprivacy.Figure 3.2: Typical Blocks in our SystemSupernode CoordinationAs shown in Figure 3.3, our D2D network consists of users with smart devices and a su-pernode at the base station (BS). Communications between user devices are through directD2D links like Bluetooth or WiFi Direct, and communications between user devices andthe supernode (e.g., reporting mobility and task information) are through a cellular link like4G or LTE. D2D task cooperation is coordinated by the supernode bearing the mobility and41Figure 3.3: Task Scheduling in the D2D Networktask information among users in mind. In this work, we assume that some necessary in-formation related to a properly sliced task piece (including some overhead and necessary42execution files, which are assumed to be of limited size not comparable to large multimediacontent) will be sent from a requester to a helper, and the calculation result (which is evensmaller) will be sent back to the requester once the helper has finished. The informationexchanged between a user node and the supernode will be of a much more limited size,whose transmission time can also be negligible compared to the cooperative task executiontime. More importantly, the D2D task cooperation is coordinated and assigned by the su-pernode at the base station, meaning that each helper is assigned specific time slots and acorresponding amount of work to help each requester. Thus, we do not emphasize the diffi-culty of assigning dedicated in-band channels for the D2D communications in our system.Instead, we emphasize the difficulty of a user executing her/his own task in a timely man-ner, and since our system is not proposed for content sharing that is bandwidth significant,we assume that D2D communications between user nodes use dedicated in-band channelsassigned by the supernode. Hence, mutual interference is not emphasized in our work.Roles of System UsersWe may further divide system users into computational resource users and miners. Minerswill write transactions into the main blockchain and are granted credits for keeping ourblockchain-based ledger system safe. Computational resource users consist of requestersand helpers: requesters in a task period are devices in need of computational assistance, andhelpers are devices that may offer help to requesters. Each successful computational assis-tance will be recorded as a transaction and will be written into the blockchain. Therefore,a requester will need to pay the corresponding amount of credit to a helper after receivingthe computational assistance from that helper.A spare user may switch between a helper and a miner according to whether task co-operation is needed in the surrounding area. When a device is assigned work to help arequester in the D2D network, the device will switch to helper mode; otherwise, i.e., when43no task is assigned to assist a helper in the current period, the device will switch to minermode in search for a mining possibility. The debate between how secure the mining algo-rithm is compared to those used in Bitcoin or other PoW-based systems remains beyondthe scope of this work.3.2.3 Overall Working ProcessIn our system, the supernode will not only issue task assignments to devices in the D2Dnetwork, it will also work as a coordinator between a requester and helper pair by acknowl-edging their cooperation work. As shown in Figure 3.3, the step-by-step working processis as follows:1. A requester notifies the supernode at the BS about the need for a cooperative task T .2. After calculation and analysis of the system conditions, the supernode will assign,say, 30% of cooperative task T to one helper and 70% of T to another helper aroundthe requester. The supernode will notify the requester and each related helper aboutthe cooperation assignment information. The requester then will send correspondingtask portions to each assigned helper.3. Each helper executes the task portion on the device.4. Upon completion, each helper will notify the supernode and send back the result tothe requester.5. When the requester gets back the computational result from a helper, she/he willnotify the supernode about the successful reception of the result.6. A transaction of the requester paying each related helper is confirmed by all three: therequester, the helper and the supernode. All three of them will store this transaction44into their own transaction pool, waiting for a miner to put this transaction into theblockchain.3.3 Problem FormulationAs mentioned in the previous section, we assume that a supernode with enough capacity ispresent at the BS covering the D2D network of our interest. At the beginning of each taskperiod, the supernode will, with the knowledge of all devices and tasks in the D2D network,calculate the probability distribution of the connectivities between devices, and assign com-putational tasks to each helper or requester device accordingly. The task assignment alsotakes into account users’ credit balance now that our blockchain-based ledger system isadopted. In addition to the connectivity-awareness, computational task assignment, andresponse delay optimization formulated in Chapter 2, our blockchain-empowered ledgersystem, selfishness avoidance, and the modified overall optimization problem are mathe-matically formulated in this section.3.3.1 Blockchain-Empowered Ledger SystemIn contrast to a Bitcoin system, where later, the user is discouraged from joining due to thesignificantly increased difficulty to obtain a new coin, our system offers the same initialcredit, ϖ , to any new user to the system. Users need to pay credits from their own balanceto get help from peers and will earn credits after helping peers on computational tasks. Atthe beginning of each task period Ψ ∈ {1,2,3, ...}, the credit balance BΨk of each user uk isobtained by the supernode by referring to the blockchain. For each user uk in period Ψ, wedenote the amount of help received by peers as RΨk , the amount of work contributed to peersas HΨk and the block reward as ηΨk . For simplicity, we limit a user to be either a requester,a helper or a miner within a given task period Ψ. In our blockchain-empowered ledger45system, uk needs to pay αRΨk from and is rewarded βHΨk to the balance BΨk ; therefore,BΨ+1k = BΨk −αRΨk +βHΨk +ηΨk , Ψ≥ 1,ϖ , Ψ= 0.(3.1)3.3.2 Selfishness AvoidanceAs derived in Section 3.3.1, the balance of each user is updated as represented in (3.1).When computing cooperative task assignment for the D2D network at each task period, thesupernode needs to make sure that each requester has enough balance for the task periodaccording to the task assignment matrix M in that period Ψ. Since the exact amount of RΨkand HΨk for user uk is not known at the beginning of task period Ψ, the supernode ideallyneeds to make sure that:Pr(BΨk −αRΨk +βHΨk +ηΨk ≥ 0)≥ ξ ,∀k ∈ {1,2, ...,u},Ψ≥ 1, (3.2)where ξ → 1. However, though the exact amount of RΨk and HΨk for user uk is not known atthe beginning of task period Ψ, their expected value, namely RΨ,expk and HΨ,expk , can easilybe obtained in advance from Mexp in that period Ψ:RΨ,expk =φk/t∑t=1h∑j=1MΨ,expk, j,t , (3.3)and:HΨ,expk =p∑i=1φi/t∑t=1MΨ,expi,k,t . (3.4)46For simplicity, we will relax the constraint (3.2) to the following:BΨk −αRΨ,expk +βHΨ,expk +ηΨk ≥ 0, ∀k ∈ {1,2, ...,u},Ψ≥ 1. (3.5)This way, user connectivity has been taken into account, and more cooperation is expectedto be done, while leaving the possibility that a user’s balance becomes lower than zero aftertask period Ψ such that the user will need to earn back enough credit before asking formore help.3.3.3 Overall Optimization ProblemTherefore, our modified optimization problem becomes:Minimize:p∑i=1texpiSubject to: (2.7−2.11)(3.1)(3.3−3.5).(3.6)As a modified optimization problem from that in Chapter 2, calculation of the optimal com-putation assignment matrix M is as well similar to the famous knapsack problems that isNP-hard [29]. That is, the computational powers of helper devices are like knapsacks withdifferent sizes, and the computational tasks from requesters are like items with differentsizes. Thus, solving for the optimal solution for the task scheduling resembles solving foran optimal solution for the knapsack problem: it is NP-hard. For effectiveness, especiallyconsidering the trend of an increasingly massive number of smart mobile devices in D2Dnetworks, we proposed a light-weight heuristic algorithm to efficiently find the sub-optimalsolution for the computation assignment matrix M illustrated in Algorithm 2 for effective-ness. Note that we make substantial use of the linprog function [35] in MATLAB forcalculating the computation assignment matrix M by transforming M element-wise into a47one-dimensional unknown vector~x with p ·(h+1) · T∆t entries from elements in M. Accord-ing to linprog [35], A, b in Algorithm 2 represent the inequality constrains for~x, and Aeq, beqrepresent the equality constrains for~x. The function get linprog parameter in Algorithm 2is transforming the constraint functions in (3.6) from a matrix from to a one-dimensionalvector form, which is basically a simple reshaping of the matrix. The lower limit for ele-ments of~x is zero and there is no upper bound for~x. The maximum wait time of a requesteris the longest time the requester can wait before she/he needs to compute the task resultherself/himself. However, it is possible that the task can be completed much sooner thanthe maximum wait time. Each iteration of Algorithm 2 tries to find lower feasible taskassignment solutions by halving (up to an integer value) a randomly-selected requester’smaximum wait time. Since the duration of each task period is limited, the maximum waittime is up to the length of a task period. Therefore, the complexity of Algorithm 2 is subjectto ln(p) ·O(linprog) where p is the number of requesters at the task period and O(linprog)represents the complexity of MATLAB’s linprog function [35]. Unfortunately, MATLABclaims improvement on efficiency of linprog over time, but releases no detail about thecomplexity. Yang in [50] claims that his algorithm on top of linprog may achieve polyno-mial complexity with the best known complexity bound on linear programming problems.3.4 Experiment and EvaluationsIn a D2D network, a variety of factors may affect the performance of our cooperativenetwork with the ledger system. In this section, we will examine the following effects:• Effect of initial credit: we vary the initial credit provided to each user to see how oursystem will be affected.• Effect of mean maximum wait time: we vary the mean maximum wait time duringthe random generation to see how the performance will be affected.48Algorithm 2: The algorithm to obtain ~φ , which corresponds to a sub-optimal solutionfor (3.6).Input: Maximum wait vector ~φOutput: Modified maximum wait vector ~φ that corresponds to a sub-optimalsolution for (3.6)1 function heuristicMaxWait(~φ)2 [A,b,Aeq,beq] := get linprog parameter(~φ)3 [x, f easible] := linprog(~0,A,b,Aeq,beq,~0)4 if f easible then5 C := {1,2, ..., p}6 while C 6= /0 do7 for random i ∈ C do8 ι := ~φi9 ~φi :=⌊~φi2⌋10 [A,b,Aeq,beq] := get linprog parameter(~φ)11 [x, f easible] := linprog(~0,A,b,Aeq,beq,~0)12 if ! f easible then13 ~φi := ι14 C := C \{i}15 return ~φ• Effect of mean task size: we vary the mean task size of each requester in a task periodduring the random generation to see how the performance will be affected.• Effect of time elapsed: we run the simulation on multiple task periods and see howsystem performance changes over time.In our simulation, we compare performance of computational resource sharing system infour different cases:• Greedy D2D task cooperation without our ledger system: without connectivity-awareness, each helper device will equally contribute its available computing powerto all connecting requesters at the beginning of a task period. For example, helper h5will assign ch53 computing power to each of p1, p3, p4 for the current task period if49and only if p1, p3, p4 are the only requesters in connection with h5 at time τ = 0.• Greedy D2D task cooperation with our ledger system: very similar to the abovecase, except that our blockchain-based ledger system is added in to enforce fairness.Therefore, the supernode at BS will check on requester balances before task assign-ment, ensuring that the assistance expected to be received by a requester will notexceed her available balance in that task period.• Connectivity-aware task scheduling without our ledger system: at the start of eachtask period, the supernode at BS will perform task scheduling calculation accordingto Algorithm 2 without our blockchain-based ledger system.• Connectivity-aware task scheduling with our ledger system: very similar to the abovecase, except that our blockchain-based ledger system is added in to enforce fairness,as illustrated in (3.5).Apart from being a reasonable incentive for users to provide help and gain credit forfuture need, the blockchain credit also provides selfishness avoidance to our system. Thatis, it prevents certain users who only want to get help from peers but not contribute to otherusers’ need. We hereof define level of selfishness, LoS, to reflect whether users have beencontributing relatively equally over task periods Ψ ∈ {1,2,3, ...,χ}:LoS=1uu∑k=1(χ∑Ψ=1RΨk −χ∑Ψ=1HΨk −ϖ)2. (3.7)In the following experimental illustrations, we show the comparison of LoS in a nor-malized way — with respect to the greedy D2D task cooperation without our ledger systemcase since LoS for this case is much larger than other three cases and it appears to be stableover the changing factors. For simplicity, the mining process is simplified to a randomselection of idle users to be miners in the network. To validate the performance of our50Table 3.1: Default Parameters - Simulation 2Number of users u 10Mean number of requester p¯ 0.4uMean number of miners 0.1uTasks period T 60sSize of time slots ∆t 5sTotal number of periods χ 30Initial credit ϖ 5000Block reward credit per task period η 50α 1β 1Maximum computation capacity cmax 100Minimum computation capacity cmin 40Computation capacity cpi or chj U [cmin,cmax]Mean task size per second σ 30 (U [15,45])Mean maximum wait time 40s (U [20s,60s])λi, j U [10−5,10−3]µi, j U [10−3,10−2]Initial connection probability at τ = 0 50%proposed system, we set up the following experiment. Default simulation parameters areillustrated in Table 3.1, where uniform distribution between two values a, b is denoted asU [a,b]. We used three real-world traces “Intel” (Trace 1), “Cambridge” (Trace 2) and “In-focom” (Trace 3) in the Cambridge/Haggle data set in [45] for our simulations. Traces 1–3were recorded by 8, 12 and 41 mobile iMotes using Bluetooth with a 30-metre radio range,respectively. Although these iMotes were not smartphones or tablets, the connection statesrecorded in these traces can be used to reproduce the dynamic topology for mobile users.The interval of each iMote sending a beacon (i.e., hello message) is 120 ± 12 s.The connectivity between mobile users is assumed to be symmetric in our work. How-ever, the connect and disconnect events in traces were recorded by each iMote individually.Thus, we consider that a pair of iMotes was connected (or disconnected) as long as oneof them detected a connect (or disconnect) event. In the real-world traces, an iMote has51recorded a connect event with a zero contact duration when it was connected with anotheriMote for a short period of time such that the iMote failed to receive two or more con-secutive beacons. Thus, for a record with the zero contact duration, we assume that theactual contact duration is uniformly distributed on [0 s, 120 s]. We concatenate the con-tact and inter-contact durations recorded by each pair of iMotes in a chronological orderto reproduce the connect and disconnect events for both of them. We then run trace-drivensimulations with the D2D topologies reproduced by all iMote pairs in each trace.3.4.1 Initial CreditThe choice of initial credit is a rather significant factor in our system. The initial creditis an indication of how much helper work can be received before a requester has to helpothers or perform mining to get system credits. If the initial credit is set too low, usersare discouraged from performing D2D cooperation. In the extreme case in Figure 3.4 andFigure 3.5, where initial credit is set to zero, the users cannot perform any D2D cooperation,resulting in a self-computing performance with a high average task execution time and noselfishness.As initial credit increases, users are encouraged to perform D2D cooperation, leadingto a fast drop in average task execution time in the two cases with our ledger system.Particularly, the average task execution time of the heuristic case with our ledger systemdrops to < 5% more than that without our ledger system, while remaining 20% less selfish.This is an indication that with a proper selection of initial credit, a little sacrifice on averagetask execution time can be exchanged for a much higher level of fairness. The greedy-creditcase has much lower LoS than that without the ledger system, but its performance is muchworse than the heuristic-credit case, implying the importance of our heuristic algorithm.520 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000Initial Credit05101520Average Run Time per Requester (s)Comparison of AlgorithmsGreedy-No CreditHeuristic-No CreditGreedy-CreditHeuristic-CreditFigure 3.4: Effect of Initial Credit on Average Task Execution Time0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000Initial Credit00. Level of SelfishnessComparison of AlgorithmsGreedy-No CreditHeuristic-No CreditGreedy-CreditHeuristic-CreditFigure 3.5: Effect of Initial Credit on Level of Selfishness3.4.2 Mean Maximum Wait TimeDuring a task cooperation in the D2D network, the requester typically wants the task to bedone in a timely manner. For example, if a requester wishes to perform a neural network-53based stock index prediction task [8] that predicts the price of a stock in 30 s, this requesterwill want to get the computation result within 30 s (could be 20 s, 25 s, etc., depending onthe specific application logic and handling behind).As shown in Figure 3.6, two heuristic cases started with a decrease in average run timefrom mean maximum wait time changing from 15 s to 20 s. This is due to that when themean maximum wait time is too low, the probability of finding a feasible solution in thecases with our heuristic algorithm is much lower. As mean maximum wait time continuesto increase thereafter, the average task execution time increases in all four cases: the en-larged solution space is increasing the difficulty of our heuristic algorithm in finding theoptimal solution; and in the greedy cases, the helpers cannot focus on helping fewer re-questers since most requesters have similarly high mean maximum wait time. Particularly,the performance on average task execution time of the greedy-credit case deteriorates ap-proximately 36% from 14 s to 19 s while that for our heuristic case with our ledger systemdeteriorates only 9% for the same change. This further proves the necessity of our heuris-tic algorithm. However, the normalized level of selfishness in Figure 3.7 all decreaseswith respect to the greedy-non credit case, with the two heuristic cases scale down faster.Comparing the heuristic cases with and without our ledger system, the sacrifice of around10-15% of average task execution can bring us at least 40% less selfishness at 50 s meanmaximum wait time and almost 100% less at 15 s mean maximum wait time.3.4.3 Mean Task SizeThe generation of task sizes in a period T is a uniform distributionU [0.5σT,1.5σT ]. Notethat it is possible that the mean task size for a requester within a period is over the comput-ing capacity of the requester device itself. Therefore, a D2D cooperation is necessary if thetask needs to be done within the maximum wait time.As illustrated in Figure 3.8 and Figure 3.9, the average task execution time all increases5415 20 25 30 35 40 45 50Mean Maximum Wait Time (s)024681012141618Average Run Time per Requester (s)Comparison of AlgorithmsGreedy-No CreditHeuristic-No CreditGreedy-CreditHeuristic-CreditFigure 3.6: Effect of Mean Maximum Wait Time on Average Task Execution Time15 20 25 30 35 40 45 50Mean Maximum Wait Time (s) Level of SelfishnessComparison of AlgorithmsGreedy-No CreditHeuristic-No CreditGreedy-CreditHeuristic-CreditFigure 3.7: Effect of Mean Maximum Wait Time on Level of Selfishnesswith respect to mean task size almost directly proportionally. The performance of ourheuristic cases starts at a very close performance at the beginning when the mean task sizeis small: a requester does not need too much assistance work from helpers, leading to a5510 15 20 25 30 35 40 45 50 55 60Normalized Mean Task Size0510152025Average Run Time per Requester (s)Comparison of AlgorithmsGreedy-No CreditHeuristic-No CreditGreedy-CreditHeuristic-CreditFigure 3.8: Effect of Mean Task Size on Average Task Execution Time10 15 20 25 30 35 40 45 50 55 60Normalized Mean Task Size00. Level of SelfishnessComparison of AlgorithmsGreedy-No CreditHeuristic-No CreditGreedy-CreditHeuristic-CreditFigure 3.9: Effect of Mean Task Size on Level of Selfishnessrelatively lower level of selfishness and average task execution time. When the mean taskdemand from requesters increases, the level of selfishness in the heuristic case without ourledger system increases much faster than that with our ledger system. When the normalized56mean task size is 60, though the heuristic case without our ledger system is 15% better onthe average task execution time, it is yet more than 250% higher in the level of selfishness.This shows how important it is to use our ledger system to enforce fairness among users.3.4.4 Time ElapsedHere, time elapsed is represented in the unit of the number of task periods elapsed. Effect oftime elapsed generally gives an idea of how the performance of the four cases will stabilizeover time.As shown in Figure 3.10 and Figure 3.11, the performance of our ledger system starts tostabilize beyond the point of the 50th period. As the task period goes on, our blockchain-empowered ledger system maintains a good level of selfishness with decreasing normal-ized selfishness, while the cooperative system without the blockchain-empowered ledgersystem, regardless of whether or not our heuristic algorithm is used, builds up more andmore selfishness. Although the performance of the heuristic-credit case on the averagetask execution time is around 20% worse than that without our ledger system, the level ofselfishness of the case without our ledger system is more than three times higher. There-fore, the adoption of our ledger system is highly recommended to enforce fairness in thenetwork.3.5 SummaryIn this chapter, we build a blockchain-empowered ledger system on top of the connectivity-aware computational resource sharing system in the D2D network. A supernode at the basestation, with knowledge of user mobilities and thus the probability model of device connec-tivities, will perform task scheduling to reduce average task execution time for requesters inthe network and enhance user QoE. Based on the blockchain-based ledger system, selfishusers who only want to get help from peers, but not contribute, will not be assigned any5710 20 30 40 50 60 70 80 90 100 110Number of Periods0246810121416Average Run Time per Requester (s)Comparison of AlgorithmsGreedy-No CreditHeuristic-No CreditGreedy-CreditHeuristic-CreditFigure 3.10: Effect of Ongoing Number of Periods on Average Task Execution Time10 20 30 40 50 60 70 80 90 100 110Number of Periods00. Level of SelfishnessComparison of AlgorithmsGreedy-No CreditHeuristic-No CreditGreedy-CreditHeuristic-CreditFigure 3.11: Effect of Ongoing Number of Periods on Level of Selfishnesshelper assistance if their balance is not sufficient. The supernode also possesses a publiclyaccessible transaction pool for miners’ reference on building up a trustworthy blockchainnetwork. Simulation results based on a realistically examined mobility model show that58our system substantially reduces average task execution time for requesters in the D2Dnetwork. Sacrificing a minor amount of average task execution time allows the system toremain at a rather low level of selfishness. To enforce fairness and encourage users, theadoption of our ledger system is highly recommended. With the help of blockchain tech-nology, our system becomes more favourable for users by providing incentives to helpersand enforces fairness among users.59Chapter 4Realizing a DecentralizedComputational Resource SharingSystem4.1 OverviewIn previous chapters, we made an effort towards a blockchain-empowered computationalresource sharing system in the D2D networks. However, shortcomings behind a PoW-based ledger system can still render the resource sharing system unrealistic.First, though the creative application of PoW consensus model started the new era forblockchain, it is also criticized with its energy inefficiency nature: all participating nodes inthe PoW network are doing useless mathematical work for the privilege in creating blocks,which costs tremendous amount of electricity. For example, annual energy consumptionindex for Bitcoin mining alone is 11.8% more than that of Switzerland, and ∼30% thatof Australia with a landmass of more than 7 million square kilometres.1 Also note that1 energy consumption is still fast growing for Bitcoin at a rate of >500% from May,2017 to May, 2018. In fact, a recent research [44] predicts that Bitcoin transactions mayconsume as much electricity as Denmark by 2020. Even worse, this electricity consumptionis eventually paid by all users through high transaction fees.Moreover, low transaction throughput is yet another problem for PoW systems. Onearea with extensive research is to improve the transaction throughput to another level, whichis beneficial for areas involving frequent interactions like sharing of bandwidth and com-puting power. For instance, Bitcoin-NG is a protocol based on the original Bitcoin. Theyboth are protocols based on sequential blocks, but instead of all miners competing for theright to produce next single block, miners are competing for the right to produce blocksfor the next epoch. There are a few key flaws of Bitcoin-NG, one being the difficulty tofigure out whether a double spending transaction is due to a malicious attempt, or due todata transmission delay. In addition, since a miner wins decisive right to produce blocksfor a relatively long period of time, it is a natural allure to invest more computing powerin exchange for more decisive power. In this case, Bitcoin-NG is prone to Bitcoin thatsubstantial amount of power gets wasted – even if less severe than Bitcoin. PoS is a way toalleviate the waste in computing power but is suspected for centralization since the richeran entity is, the more power this entity holds, which is similar to a centralized case (Google,Apple, central banks as examples). An even more crucial issue of PoS is the rational forksproblem as explained in Section 1.1.2. DPoS is an improvement from PoS that to a largeextent solves the rational forks problem, but it comes at a cost of sacrificing even moredecentralization.DAG-based blockchains are believed to represent the direction for blockchain technol-ogy for the future. In most of existing systems implementing DAG-based consensus, thereare no miners, and therefore no transaction fees. New transactions are created to confirm61existing transactions without PoW2, which saves a great deal of computing resource. An-other significant advantage of DAG is higher transaction throughput, as the system doesnot need to wait for miner packaging. Consequently, leading pioneers in the DAG fieldlike IOTA [42] and Nano [33] have put extensive amount of research in DAG to enhancetransaction throughput to another level.According to the IOTA white paper, the consensus algorithm governing the health ofthe system is the Markov chain Monte Carlo (MCMC) algorithm to select transactions toverify before a new transaction can be made. This algorithm tries to eliminate phenomenalike participant laziness and secret side chain forming (to double spend). The true effectof MCMC remains to be justified, but since the MCMC heavily relies on the cumulativeweight profile of the whole DAG (called the tangle in the IOTA white paper [42]), thealgorithm is extremely costly both in time and memory space. Further, IOTA claims that thecurrent system is under mature, and is thus in need for a coordinator verifying transactionsproperly. Such a closed-source coordinator is after all a centralized governing authorityfor now. Even though the ultimate goal of IOTA is to remove the central coordinator, thecumulative weight dependence still renders the whole system in question. Here in thischapter, we will illustrate the problems of IOTA, and propose a buffer system to overcomethese issues. We try to realize a decentralized computational resource sharing system in theD2D networks by adopting a much more cost-effective type of DAG-based ledger system.4.2 System ModellingIn this section, we will present the basic system settings and background formulations forthe buffer mechanism of our system. Note that the following terms are used interchange-ably: “node”, “user”, “participant”, and “device”.2Some DAG-based systems are implemented with a minor amount of PoW (mostly for spam protection)that is negligible when compared to Bitcoin and other PoW-based systems.624.2.1 Nodes, Accounts, and BalancesThere is a set of n nodes, denoted as U = {u1,u2, ...,un}, corresponding to each of theparticipating devices in the D2D network. For simplicity, we divide our system nodes intotwo categories in this work:• Full nodes: system participants that keep the full transaction history including thegenesis3.• Light nodes: system participants that keep only a minor portion of the full transactionhistory.Apparently, full nodes are more resistant to malicious actions as they are able to verify anytransaction against the full history themselves.4 A light node can keep only a minor portionof the transaction history to function seemingly as a full node.Each user is associated with an account, and is identified by other users with a unique160-bit account address.5 In existing blockchain applications, there are generally two waysto indicate the spending power of an account: UTXO model or balance model. An UTXOis an output of a transaction that has not been spent or sent to anyone. In UTXO model,which is used in Bitcoin and our ledger system in Chapter 3, spending power of an accountis indicated by the aggregate of UTXOs of this account. In balance model, which is usedin Ethereum, spending power of an account is indicated by the account balance. In com-parison with the UTXO model used in Bitcoin for payment verification, our system adoptsa balance model similar to that in Ethereum. Even though UTXO model provides better3the only system-generated transaction created at the very beginning of the system4There may be debate on the negative effects of the size of the full history to be stored on a full node.This is a common question for any of the existing blockchain systems. There are also various ways to storethe full history other than storing it all locally, e.g. storing it in a distributed way. The storage optimizationproblem remains outside the scope of this work.5In general, there is no restriction on the number of accounts a user can create. But for simplicity, welimit that a user has only 1 account in this work.63privacy to some extent, we are still in favour of a balance model due to its simplicity andefficiency. Therefore, each node in our system keeps a balance mapping for all users.64.2.2 Transactions and Transaction ConfirmationsAt any discrete time moment τ , the k’th user uk will issue xk transactions {vuk1 ,vuk2 , ...,vukxk}into the network, where xk ∈ N is a non-negative integer. Thus, there will be λ =n∑k=1xknew transactions in total issued at moment τ . To issue a new transaction, a node is requiredto: 1) indicate the last issued transaction, and 2) confirm the validity of s existing transac-tions, where s ∈ N+ is a positive integer, as shown in Figure 4.1. We define the last issuedtransaction to be the “biological” parent (BioP) of the new transaction, and the s confirmedtransactions to be the “adoptive” parents (AdoPs) of the new transaction. It is clear thatFigure 4.1: New Transaction Issuances = 1 means a node can easily keep issuing new transactions that confirm her own trans-actions, which discourages the network from co-operating and renders the system useless.On the other hand, if s gets too large, each new transaction may need to spend too muchtime and effort confirming many existing transactions, which effectively downgrades the6In general, a light node may choose to only keep balances for active users. For simplicity, we assumelight nodes also keep balances for all users in this work.64performance of the system. For a realistic decentralized system, we impose s ≥ 2, and sets= 2 by default in our system. The very first transaction of the system, the genesis G , is theonly transaction created by the system itself at the beginning, and is the only transactionwithout any parents.74.2.3 Graph of TransactionsNow consider a transaction graph G= {V,E}where the vertex setV is the set of all transac-tions and the edge set E the set of all direct confirmations from one transaction to another.Shown in Figure 4.2 is part of the transaction graph G, where each vertex (box) representsa transaction, and each edge represents a confirmation relationship8. Each transaction isuniquely identified by a transaction ID that is generated according to the information con-tained in the transaction, e.g. sender and receiver addresses, amount of token to be trans-ferred, ID of transactions that have been confirmed, etc. This uniqueness of a transactionmeans that changing a transaction’s confirmations is not possible (as it would change thetransaction ID and makes it a distinct new transaction), leading to the fact that a cycle inthe graph of transactions is not possible. Since the graph of transactions is directed andcycle-free, it is a directed acyclic graph (DAG).Path and DistanceA path p in G from transaction v0 to another transaction vl is the set of ordered vertexesp= (v0,v1,v2, ...,vl−1,vl) between them such that (v0,v1) ∈ E,(v1,v2) ∈ E, ...,(vl−1,vl) ∈E are all satisfied. Length of the path p, denoted as lp, is |p|−1 where |p| is the cardinalityof p. In this case, lp = l. For example, as illustrated in Figure 4.2, a path p= (v0,v1,v2,v3)7If there is only one single genesis transaction at the beginning, there may be confusion regarding too fewtransactions to confirm for the first set of user-generated transactions. To avoid such confusion, there willin fact be, instead of one single genesis transaction, a set of genesis transactions generated by the system upfront. For simplicity, we refer to this set of genesis transactions as the genesis.8The biological relationship between 2 transactions is not a confirmation relationship. Therefore, theedges in the graph of transactions are all adoptive relationship.65Figure 4.2: Graph of Transactionswith length 3 starts from transactions v0 and ends at transaction v3. A path can also berepresented with the edges between two vertexes, such that p= (v0,v1,v2,v3) = (e0,e1,e2)in Figure 4.2.The set of all possible paths from one transaction v to another transaction v∗ is denotedas P(v,v∗). If a path from v to v∗ is not possible, P(v,v∗)= /0. Due to the directed and acyclicnature of G, all paths between v and v∗ are in the same direction such that if P(v,v∗) 6= /0,then P(v∗,v)= /0 (the reverse does not necessarily hold true). Distance from v to v∗, denotedas dv,v∗ , is the length of the shortest path between them, or −1 if no path between them,66i.e.:dv,v∗ =minp∈P(v,v∗)lp, P(v,v∗) 6= /0;−1, P(v,v∗) = /0.Note that, in addition to path, distance is also directed, such that if dv,v∗ > 0, then dv∗,v=−1.Indirect ConfirmationIf one transaction v directly confirms another transaction v∗, there is a path (v,v∗) ∈ E oflength 1 between them such that dv,v∗ = 1. In this case, as defined in Section. 4.2.2, v∗ isan adoptive parent (AdoP) of v. In comparison, if v indirectly confirms v∗, there is a pathbetween them whose length is greater than 1. That is, v indirectly confirms v∗ if and onlyif dv,v∗ > 1. In Figure 4.2, v0 directly confirms v1 and indirectly confirms v2 and v3.SubgraphA subgraph9 G′ = {V ′,E ′} of a graph G = {V,E} (G′ ⊂ G) is a graph such that V ′ ⊂ Vand E ′ = {(u,v)|u,v ∈ V ′ ∧ (u,v) ∈ E}. For example, there are two subgraphs related toany transaction v in the graph G — the “past” and “future” transaction sets of v, denotedas P(v) and F (v) respectively. P(v) is the set of all transactions that are directly andindirectly confirmed by v, andF (v) is the set of all transactions that directly and indirectlyconfirmed v:P(v) = {v∗|dv,v∗ > 0},F (v) = {v∗|dv∗,v > 0}.Note that v /∈P(v) and v /∈F (v). Please also note that the following conditions equiva-lently mean “v directly or indirectly confirmed v*”:1. v∗ ∈P(v);9In this work, we assume that any subgraph of G is a proper subgraph for simplicity.672. v ∈F (v∗);3. P(v,v∗) 6= /0;4. dv,v∗ > 0.Dimension of a GraphThe dimension of a graph is characterized by the ceiling and the floor of the graph. Theceiling of G, denoted as G, is defined to be the set of transactions in G without any parent,and the floor of G, denoted as G, is defined to be the set of transactions in G without anychild, i.e.:G= {v ∈ G|P(v) = /0},G= {v ∈ G|F (v) = /0}.The transactions in G are called the “tops” of G, and the transactions in G are called the“tips” of G. For a graph G shown in Figure 4.3, the 4 blue transactions are the “tops” of G,and they together form the ceiling of G. Similarly, the 3 green transactions are the “tips” ofG, who together form the floor of G.The set of all paths in G = {V,E} is defined as P(G) = ⋃v,v∗∈VP(v,v∗). A path p is alongest path in G if and only if its length is the longest over the set of all paths in G, i.e.lp = maxq∈P(G)lq.Lemma 1. If a path p= (v, ...,v∗) is a longest path in graph G, then v ∈ G and v∗ ∈ G.Proof. 1) If v /∈ G, one can find at least one child v− of v such that there must be a pathp− = (v−, p) = (v−,v, ...,v∗) with length lp− = lp+ 1. Therefore, length of p is at leastshorter than p− and p must not be a longest path in G.2) If v∗ /∈ G, one can find at least one parent v+ of v∗ such that there must be a pathp+ = (p,v+) = (v, ...,v∗,v+) with length lp+ = lp+ 1. Therefore, length of p is at least68Figure 4.3: Dimension of Graphshorter than p+ and p must not be a longest path in G.According to Lemma 1, a longest path in G must start from the floor and end at theceiling of G. We hereby define the height of G, denoted as hG, to be the length of thelongest path in G, and according to Lemma 1, we have:hG = maxp∈P(G)lp = maxv∈G,v∗∈G,p∈P(v,v∗)lp.In Figure 4.3, we can find a path (v0,v1,v2,v3) that is longest possible in G, which leads tohG = 3.The start of a longest path in G is called a “true tip” of G, and the end of a longest pathin G is called a “true top” of G. Clearly, the set of true tips is a subset of the set of tips, and69the set of true tops is a subset of the set of tops. In case of the graph in Figure 4.3, all topsare true tops and all tips are true tips.Reverse GraphGiven an edge e = (v−,v) from v− to v, the reverse of this edge, denoted as ¬e is an edgefrom v to v−, i.e. ¬e = (v,v−). A reverse graph of G, denoted as ¬G, is a graph with thesame set of vertexes but the direction of all edges reversed. Since the direction of an edgeis from a child to its parent in a transaction graph, the direction of an edge in a reversetransaction graph is from a parent to its child.4.2.4 Other AspectsChronological Order of TransactionsThe chronological order of transactions is a very common question for existing blockchainsystems. Due to the decentralized nature, determining the chronological order of trans-actions is substantially harder than a centralized system since there is no central servercontrolling the intake of new transactions. For instance, in a miner-based blockchain sys-tem, e.g. PoW and PoS, the block order does not necessarily represent the chronologicalorder of transactions, since the block order is solely determined by the miners that createdthese blocks. For example, a miner may choose to pack a later transaction first because itcontains higher transaction fee. In our DAG-based system, there is no definite chronologi-cal order for all transactions in the DAG either. However, there is an definite chronologicalorder between 2 transactions if one transaction directly or indirectly confirms the other.That is, for 2 transactions v and v∗, if v∗ ∈P(v) (or equivalently v ∈ F (v∗)), then v∗comes earlier than v, or v is a later transaction than v∗. For instance, in Figure 4.3, v0 is alater transaction than all v1, v2, and v3.70Height of a TransactionIn our system, even though the relative chronological order between 2 transactions is def-inite provided that one directly or indirectly confirms the other, it is very common that 2transactions present no confirmation relationship between each other. For instance, thereis no confirmation relationship between v0 and v4 or between v0 and v5 in Figure 4.3, suchthat chronological relationship cannot be determined definitely. As a contribution to de-termining chronological order of transactions to some extent, we introduce the height of atransaction as an important reference for the chronological order among transactions.In our definition, the height of a transaction in a graph is the height of the graph lessthe length of the longest path from this transaction to the ceiling of the graph. Clearly,the height of a transaction in the ceiling would have a height that is equal to the height ofthe graph, and the height of a transaction in the floor would have a height that is equal tozero. The height profile of a transaction graph can be determined with the topological sortof the graph. A topological sort or topological ordering of a DAG is a linear ordering ofits vertexes such that for every edge (v,v∗) in the DAG, v comes before v∗ in the ordering.Running time of a topological sorting of a graph G = {V,E} can be achieved linear in thenumber of vertexes plus the number of edges in the graph, asymptotically O(|V |+ |E|)[28]. There are different implementations of a topological sorting algorithm, most notablythe Kahn’s algorithm [28] and a depth-first search algorithm proposed by Cormen et al. in[13], all with time complexity O(|V |+ |E|).Our algorithm to obtain the height profile of a transaction graph G= {V,E} adopts theKahn’s algorithm, as illustrated in Algorithm 3. Note that in the algorithm, the graph G isrepresented as a hashmap dictionary whose keys are transactions in V , and the value of akey being the set of transactions the key points to. Therefore, an edge implicitly presents ina key-value pair, if the value is non-empty. In the algorithm, one just need to check for keys71with values as empty sets to obtain the set, O, of vertexes with no incoming edge. WithAlgorithm 3, the height of a transaction v in graph G is defined to be the index of the set vresides in in L.Algorithm 3: The algorithm to obtain the height profile of a transaction graph.Input: Transaction Graph G= {V,E}Output: A list L of sets of transactions, such that for every edge (v,v∗) in G, vpresents in a set before the set v∗ resides in.1 function toposort(G)2 L := Empty list3 O := Set of all vertexes with no incoming edge in G4 while O is non-empty do5 append O to L6 remove O from G7 O := Set of all vertexes with no incoming edge in G8 return LWeight of a TransactionEven though the weight of a transaction is not utilized in our system, as we consider thatupdating the weight profile of a transaction graph takes a long time, we will introduce theidea of the weight of a transaction that is commonly used in many DAG-based blockchainsystems, and explain the reason why it is not adopted in our system.In many DAG-based blockchain systems such as IOTA, a small amount of PoW isrequired from a node before issuing a new transaction. Such a PoW requirement mainlyaims at preventing malicious parties from flooding the network since there is no economicobstacle, e.g. transaction fees, imposed. From the IOTA white paper [42], own weight of atransaction v, denoted as ω(v), is defined to be positively correlated to its amount of PoWperformed.Cumulative weight of a transaction v, denoted as Ω(v), is the sum of own weights ofall transactions in F (v) (that directly and indirectly confirmed v), plus the own weight of72v itself. If own weight of any transaction is set to 1,Ω(v) = ∑v∗∈F (v)ω(v∗)+ω(v) = |F (v)|+1.For simplicity, we set the own weight of a transaction v to be 1, i.e. ω(v) = 1.Recognized TransactionsA transaction is deemed recognized by a node if it has been transmitted to the node andincluded into the local DAG of the node. In our system, a recognized transaction sits in theaccepted graph (AG) or the buffered graph (BG) of a node, where AG and BG are to beexplained in the following section.4.3 The Accepted Graph and the Buffered GraphIn our design, instead of a single DAG representing the set of all recognized transactions(like a tangle in IOTA), each node would have the set of all recognized transactions dividedinto 2 portions: the AG and the BG, as shown in Figure 4.4.For each individual user, the AG, as the name suggests, is the set of transactions ac-cepted, and the BG is the graph of buffered transactions pending acceptance. Note that theBG is limited by a maximum height while the AG is not. The edges pointing from the BGto the AG do not belong to any of the two graphs. Transactions are categorized into 4 types:• new transactions: transactions that have not been recognized;• buffered transactions: transactions that have been buffered and pending acceptance;• accepted transactions: transactions that have been accepted;• ejected transactions: transactions that have been ejected, usually due to bad synchro-nization with the network or malicious attempts.73Figure 4.4: Accepted Graph and Buffered GraphIn comparison to the more straightforward AG, the BG works as a buffer for a nodewhen dealing with new transactions. The main purposes for the buffer in our system are:1) to eliminate lazy nodes, and 2) to eliminate parasite chain attack or double spending, tobe explained in the following sections. In this section, we use G to represent a BG.744.3.1 Dimension of the BufferThe width of a BG G, denoted as wG, is defined as the number of transactions in the floorof G, i.e.:wG = |G|.Therefore, if Figure 4.3 represents a BG, the BG is dimensionally characterized by a heightof 3 and a width of 3. A BG can build up its height and/or width by adding more trans-actions into the BG. However, for each BG in our system, we impose a maximum heighthmax such that no node should have the height of its BG go beyond the hmax.4.3.2 Maturity and Buffered Graph AdvancingIn addition to hmax, we also impose a minimum width wmin to characterize the maturity of aBG. Once a BG achieves a maximum height and a minimum width, this BG is regarded as“matured”. Since the height of a BG is capped, we progress the system by letting the BGsperform “buffered graph advancing” on maturity. To be specific, once a BG gets maturedwith hG = hmax and wG >= wmin, this BG may be advanced. Advancing the BG means totransfer all the tops of BG to the AG — in other words, to accept these top transactions.Right after the advance, height of the BG is shorten by 1, and nodes should be building upthe height again for the next advance. In such way, nodes are building up their AGs and thesystem can progress.4.3.3 Consensus over the Buffered GraphWe now need to impose a consensus in the network such that the BG can serve the purposesof 1) eliminating lazy nodes, and 2) eliminating parasite attack or double spending:1. The biological parent (BioP) of a new transaction should be recognized.2. The AdoPs of a new transaction should both be in the BG.753. The balance of the sender of a new transaction should not be lower than 0 after thetransaction.4. Advance the BG when it achieves maximum height and minimum width.Requirement #1 of the consensus is to serve the purpose of flooding-prevention. Whena node tries to flood the system by issuing a lot of transactions suddenly, all but the firsttransaction would not have their BioPs recognized by peers, which becomes the only trans-action taken into account. Requirement #2 of the consensus is to serve the purpose of lazynode prevention because if a node does not confirm an up-to-date transaction (up-to-dateenough to be in the BG of peers), it can easily get rejected by peers as its AdoPs are deepinto the AG and no longer appears in the BG of peers. Requirement #3 serves the purposeof double-spending prevention, and Requirement #4 is to progress the BG properly and ina timely manner.4.3.4 Parent SelectionIn order for a user’s new transaction to get accepted by a peer, this transaction needs to firstget recognized into the BG of the peer, which includes a requirement to have its AdoPs bothin the peer’s BG. This requirement ensures that a new transaction should verify transactionswithin the BGs of peers. Assuming zero latency among users, or full synchronization suchthat BGs of all users are identical, a user should always verify two transactions in her ownBG. Considering the case with significant latency, the best chance for a user would be toreference true tip transactions in her own BG.In IOTA, a node runs an MCMC algorithm to select two unconfirmed transactions asthe parents of a new transaction, whose details are illustrated in Section 4.1 of [42].4.3.5 Graph Update AlgorithmA lot of dimensional information of the BG is important to a node:76• height and width: indication of the maturity of the BG;• tops (including true tops): the portion to get advanced into the AG;• tips (including true tips): for the parent selection process.To get the above information, we designed the following BG update algorithm that is basedon Algorithm 3:Algorithm 4: The algorithm to obtain the dimension information of a buffered graph.Input: Buffered graph GOutput: height h, width w, tips T1, true tips T2, tops T3, true tops T41 function get dimension(G)2 L := toposort(G)3 ¬L := toposort(¬G)4 T1 := L(0)5 T2 := ¬L(−1)6 T3 := ¬L(0)7 T4 := L(−1)8 h := length(L)9 w := length(T1)10 return h,w,T1,T2,T3,T4Note that L(0) means the first element in the list L, and L(−1) is the last element in thelist. As explained in Section 4.2.4, time complexity of “toposort” in Algorithm 4 is linearto the number of transactions and confirmations in the BG. Therefore, the complexity ofAlgorithm 4 itself should also be linear to the number of tranasctions and confirmations tothe BG.In comparison, IOTA, with many similar DAG-based systems, rely on the cumulativeweight profile of the DAG. Specifically, the MCMC algorithm of IOTA need the cumu-lative weight profile of the whole DAG without a coordinator. Such an algorithm is quiteexpensive in terms of execution cost, which will be presented in Section 4.4.774.3.6 Lazy Nodes and Parasite Chain AttackWhen a node tries to be lazy by not confirming up-to-date transactions, its AdoPs arelikely to have been deep into peers’ AG. In such case, this node’s new transaction willnot be added into the BG by a peer, and therefore has no chance of being accepted intothe AG. A parasite chain attack is when a node secretly builds up a long side chain oftransactions confirming a double spending transaction, but broadcasts the chain only afterthe the original transaction gets confirmed by the receiver, as defined in [42]. Note thatthis sort of parasite chain attack is not limited to DAG-based systems like IOTA. In fact, itis similar to a side chain attack in PoW-based systems, where a powerful malicious partysecretly builds up a long side chain. In our system, a parasite chain would not work sinceas the system progresses, the AdoPs of the first transaction in a parasite chain would havebeen deep into the AG of system nodes, which prevents this transaction from being takeninto the BGs (and therefore the AGs) of peers. When the first transaction of the parasitechain is not recognized by a peer, none of the future transactions will be accepted. Overall,the BG serves the purpose of preventing lazy nodes and parasite chains in the system.4.4 Experiment and EvaluationsIn this section, we set up an experiment to examine the performance of our decentralizedledger system. Note that no miners are needed in our system so that a node can be eithera requester or a helper. In order to focus on analyzing the performance of the DAG-basedledger system itself in terms of transaction throughput, we assume that any node, at anytime step, issues a transaction with a given probability. We first investigate how the di-mension of the BG affects the performance of our decentralized ledger, then compare thesystem with a simulated decentralized IOTA system, and finally explore the dynamics ofour buffer system. Default simulation parameters are illustrated in Table 4.1.78Table 4.1: Default Parameters - Simulation 3Number of nodes n 20Maximum height hmax 8Minimum width wmin 20Total number of time steps T 100Probability of new transaction issuance p 50%Mean transmission delay d 2 time stepsMean # new transactions per time step λ np4.4.1 Buffer DimensionFigure 4.5: Parameter Effect of wminFor each node in our DAG-based ledger system, dimension of the BG may directlyaffect the transaction throughput. Therefore, we try to investigate how the minimum widthand the maximum height of the BG affect the performance of our ledger system. In thispart, we assume all nodes use the same minimum width and maximum height.As illustrated in Figure 4.5 and Figure 4.6, we vary the maximum height and minimum79Figure 4.6: Parameter Effect of hmaxwidth of the BGs of all nodes. Clearly, after the BG gets filled up, the average time neededfor a new transaction steps into saturation. As the size of the BG increases, i.e. as either theheight or the width increases, the saturated average time increases. After saturation, thereis a “teeth” area shown in the graph. The tip of a tooth is an indication of an advance ofthe BG: directly after an advance, the size of the buffer temporarily drops down, and thengets filled up again. It is interesting that the increase in width results in a linear increasein average time for a new transaction while the increase in height is somewhat superlinear,and the tooth size is also different. This is due to the reason that an advance pushes theceiling of the BG into the AG, and a fatter BG, thus wider ceiling, gain more temporaryrelief in size after an advance.80Figure 4.7: Comparison with IOTA4.4.2 Comparison with IOTAIOTA is generally recognized as the leader in DAG-based blockchain systems as they arethe first to launch a global DAG-based blockchain project with an initial coin offering(ICO). However, even though they claim to remove the closed-source coordinator in theroad map, they are still a centralized system currently. According to the system specificsin the white paper, we simulate a decentralized IOTA system to compare with our DAGsystem. In the IOTA system, we simulated 3 types of IOTA nodes: IOTA nodes withno snapshot (type 1), IOTA nodes with snapshot (type 2), and IOTA nodes with frequentsnapshot (type 3). As illustrated in Figure 4.7, IOTA nodes without snapshot will havetheir average time for a new transaction increase exponentially and indefinitely, which isby no means realistic. A snapshot may relief such issue, while the time needed can stillget severely long before a snapshot. To achieve a comparable transaction throughput as our81node (BG size: hmax = 12,wmin = 10), the IOTA nodes would need to take a very frequentsnapshot for every 250 transactions (IOTA node type 3) in our simulation. There are manyreasons the IOTA system should be deemed incapable for applications with high transactionthroughput:• Ideally, the snapshot should be taken in a synchronized manner. Otherwise, a trans-action deemed valid by one node may be deemed invalid by another node who hasjust performed a snapshot. However, synchronization in a decentralized network isrelatively hard.• The cost behind a snapshot can be high. For example, a snapshot done by IOTA,in a centralized manner, would take several hours (during which no transactions areallowed) according to their official announcement on July 9, 2018 []. Such cost makeus doubt whether the snapshot mechanism is practical for high transaction through-put, not to mention when high frequency and decentralization of snapshots are alsoneeded.• Even if the cost of snapshot can be substantially limited, it can just as well be adoptedsimilarly into our system for a higher transaction throughput.4.4.3 Transaction Confirmation TimeThe dimension of the BG is not fixed. In fact, the dimension of the BG may be altered tocope with changing environment such as increased transaction arrival rate and delay. Wetry to investigate the dynamics of BG and propose proper actions in response to changingenvironment.As shown in Figure 4.8, the average transaction confirmation time is slightly superlinearto the size of the BG, meaning that for faster transaction confirmations, the buffer sizeshould be as low as possible. A 5 times increase in the width results in a 7 times increase82Figure 4.8: Effect of Buffer Size on Average Transaction Confirmation Timein the confirmation time, while a 5 times increase in the height results in an approximately14 times increase in the confirmation time. The superlinearity in hmax is higher than thatin wmin. The reason is that, when we double the hmax, the height a new transaction needsto travel before getting accepted into the AG is also doubled, with doubled number ofadvances the BG needs to take. Note that after each advance, the node needs to updatethe BG through Algorithm 4. However, the height a new transaction needs to travel beforeAG and the number of advances remain the same when we double the wmin, which is whythe superlinearity in wmin is lower. For this reason, to cope with increased transactionarrival rate, we should increase wmin accordingly. To keep a better chronological order oftransactions in the BG, hmax should be increased to cope with longer transaction delay.834.5 SummaryIn this chapter, we build a DAG-based decentralized ledger system for our computationalresource sharing system. In stead of storing one single DAG containing all existing transac-tions, a user in our system will divide the set of all existing transactions into two portions:the AG containing accepted transactions and the BG containing buffered transactions. TheAG is a graph containing all accepted transactions by the node. The purpose of a BG is toprevent lazy nodes that does not contribute to confirming new transactions, and to preventmalicious nodes that try to perform double spending. The BG is characterized by its max-imum height and minimum width. A larger maximum height allows for a larger latencywithin the D2D network, and a larger minimum width is to cope with larger transactionarrival rate due to events such as increased number of users or a boost of cooperation re-quests. In comparison with the big leader in the field, IOTA, our system is much moreefficient in the local D2D network in terms of transaction throughput. The main reasonbehind is that the time needed to perform the MCMC mechanism in IOTA grows expo-nentially and indefinitely as the number of recognized transactions increases, but the timeneeded to perform our DAG update algorithm only depends on the buffer size, which satu-rates for given height and width. IOTA proposed a snapshot countermeasure to relieve suchissue, where a snapshot means to conclude existing transactions to a balance mapping. Toofrequent snapshot can be expensive while too infrequent snapshot increases the burden ofthe nodes and downgrades the transaction throughput. Even worse, even a single snapshotseems to be expensive enough according to [27]. For the IOTA mechanism to be realisticfor high-throughput applications in a local D2D network, it must adopt a possibly expen-sive frequent snapshot countermeasure. Experimental results show that our mechanism stillexcels the IOTA mechanisms with very high snapshot frequencies. Finally, since the shar-ing network itself is dynamic (transaction transmission delay may increase, users can leave84and join that varies transaction arrival rate, etc.), we also analyzed on the dynamics of theBG. Simulation results show that higher transaction arrival rate should be tackled by anincreased width, and increased transaction transmission delay should be addressed by anincreased height.85Chapter 5Conclusions and Future WorkIn this chapter, we summarize the results and highlight the contributions of this thesis, withseveral topics for future work suggested in Section Results and Conclusions of the Research• In Chapter 2, we proposed connectivity-awareness to mobile task cooperation in theD2D networks. With the knowledge of user mobility and probability profile of deviceconnectivity, a supernode can perform task cooperation scheduling to shorten taskexecution time for requesters.• In Chapter 3, we proposed a blockchain-based decentralized credit system to ourtask cooperation system in the D2D networks. We showed system design of suchsystem, and simulation results showed that selfish users who do not contribute totask cooperation in the system will not be assigned assistance from peers, which inturn enhances fairness within the system. Further, the significant enhance of fairnessonly sacrifices a minor amount of average task execution time.• In Chapter 4, we proposed a DAG-based decentralized ledger system. Design of86such ledger system is to solve the efficiency problem of traditional blockchain mech-anisms like PoW and PoS. Specifically, PoW is criticized for its inefficiency in bothelectric power and transaction confirmation speed. PoS is criticized for centraliza-tion and easy forks. DAG-based blockchain mechanisms are commonly recognizedas suitable for applications with high throughput. We spot the inefficiency in IOTA,a pioneer in DAG, and questioned it for practicality of IOTA without centralization.With an emphasize on the height of a transaction, instead of the weight in IOTA, weproposed a novel buffer mechanism and showed its practicality and excellence overeven the top of field, IOTA, for our application. Note that our DAG-based ledgersystem should not be limited to task cooperation in the D2D networks only. It maybe applied to other generally cooperations with high throughput requirement.5.2 Suggestions for Future WorkIn the following, we discuss several interesting possibilities for extension of the currentwork.5.2.1 Performance of Heuristic Algorithm for Task SchedulingIn Chapter 2, the performance of our heuristic task scheduling we propose is sub-optimal,and is closer to the optimal performance only when mean maximum wait time among allrequesters are small enough. The reason for adoption of our heuristic algorithm for com-putation of task scheduling is that calculation of the optimal solution is NP-hard especiallyif we have more time slots within a task period. To relieve the burden of computation timefor task scheduling, we have to sacrifice some performance over the average task executiontime. In future work, we will take success rate into account and transform our problem inthis work to an optimization problem over the success rate, which is convex and optimalsolution can be achieved within polynomial time.875.2.2 Expanding the Local NetworkThe current system is within a D2D network with limited size. In other words, the trans-action delays among users are limited. In Chapter 4, we showed that an increased systemtransmission delay can be tackled by increased buffer size. However, when the scale of thenetwork expands to a significant size, it becomes impractical to simply increase the buffersize accordingly as it may as well downgrade the system performance significantly. How toeffective extend the scale of network to allow significant transmission delay in the systembecome another open issue. One possibility is to form many small clusters of users, withinwhich the delay is limited and among which coordination is needed.5.2.3 Probability Model of Chronological Order of TransactionsEven though the overall chronological order of transactions can hardly be made definite,probability model of their chronological order may be investigated such that the chronolog-ical order of transactions can be determined with certain degrees of confidence. With suchprobability model, timestamps of transactions become possible, which allows for a morecomprehensive decentralized system.88Bibliography[1] E. Androulaki, A. Barger, V. Bortnikov, C. Cachin, K. Christidis, A. De Caro,D. Enyeart, C. Ferris, G. Laventman, Y. Manevich, et al. Hyperledger fabric: adistributed operating system for permissioned blockchains. In Proceedings of theThirteenth EuroSys Conference, page 30. ACM, 2018. → page 9[2] A. Asadi and V. Mancuso. Wifi direct and lte d2d in action. In 2013 IFIP WirelessDays (WD), pages 1–8, Nov 2013. doi:10.1109/WD.2013.6686520. → page 4[3] A. Back. Hashcash - a denial of service counter-measure., 09 2002.→ page 7[4] D. Bayer, S. Haber, and W. S. Stornetta. Improving the efficiency and reliability ofdigital time-stamping. In R. Capocelli, A. De Santis, and U. Vaccaro, editors,Sequences II, pages 329–334. Springer New York, 1993. ISBN 978-1-4613-9323-8.→ page 6[5] F. Boccardi, R. W. Heath, A. Lozano, T. L. Marzetta, and P. Popovski. Fivedisruptive technology directions for 5g. IEEE Communications Magazine, 52(2):74–80, February 2014. ISSN 0163-6804. doi:10.1109/MCOM.2014.6736746. →page 4[6] F. Bonomi, R. Milito, J. Zhu, and S. Addepalli. Fog computing and its role in theinternet of things. In Proceedings of the First Edition of the MCC Workshop onMobile Cloud Computing, MCC ’12, pages 13–16. ACM, 2012. ISBN978-1-4503-1519-7. doi:10.1145/2342509.2342513. URL → page 5[7] W. Cai, V. C. M. Leung, and M. Chen. Next generation mobile cloud gaming. In2013 IEEE Seventh International Symposium on Service-Oriented SystemEngineering, pages 551–560, March 2013. doi:10.1109/SOSE.2013.30. → page 14[8] P.-C. Chang, C.-H. Liu, J.-L. Lin, C.-Y. Fan, and C. S. Ng. A neural network with acase based dynamic window for stock trading prediction. Expert Systems withApplications, 36(3, Part 2):6889 – 6898, 2009. ISSN 0957-4174.89doi: URL → pages30, 54[9] D. Chaum. Blind signatures for untraceable payments. In Advances in Cryptology,pages 199–203. Springer US, 1983. ISBN 978-1-4757-0602-4. → page 6[10] C. A. Chen, M. Won, R. Stoleru, and G. G. Xie. Energy-efficient fault-tolerant datastorage and processing in mobile cloud. IEEE Transactions on Cloud Computing, 3(1):28–41, Jan 2015. ISSN 2168-7161. doi:10.1109/TCC.2014.2326169. → page 4[11] F. Chi, X. Wang, W. Cai, and V. C. M. Leung. Ad hoc cloudlet based cooperativecloud gaming. In 2014 IEEE 6th International Conference on Cloud ComputingTechnology and Science, pages 190–197, Dec 2014.doi:10.1109/CloudCom.2014.112. → page 5[12] A. Churyumov. Byteball: A decentralized system for storage and transfer of value.URL https://byteball. org/Byteball. pdf, 2016. → page 11[13] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Section 22.4: topologicalsort. Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pages549–552, 2001. → page 71[14] Dave Chaffey. Mobile marketing statistics compilation., 2017. Online. → pages 4, 15[15] J. Dean and S. Ghemawat. Mapreduce: Simplified data processing on large clusters.Commun. ACM, 51(1):107–113, Jan. 2008. ISSN 0001-0782.doi:10.1145/1327452.1327492. URL → pages19, 20[16] A. Y. Ding, B. Han, Y. Xiao, P. Hui, A. Srinivasan, M. Kojo, and S. Tarkoma.Enabling energy-aware collaborative mobile data offloading for smartphones. In2013 IEEE International Conference on Sensing, Communications and Networking(SECON), pages 487–495, June 2013. doi:10.1109/SAHCN.2013.6645020. → page3[17] A. Fahim, A. Mtibaa, and K. A. Harras. Making the case for computationaloffloading in mobile device clouds. In Proceedings of the 19th Annual InternationalConference on Mobile Computing &#38; Networking, MobiCom ’13, pages203–205. ACM, 2013. ISBN 978-1-4503-1999-7. doi:10.1145/2500423.2504576.URL → pages 4, 16[18] GameFly., 2017. Online. → page 1490[19] C. Gao, A. Gutierrez, M. Rajan, R. G. Dreslinski, T. Mudge, and C. J. Wu. A studyof mobile device utilization. In 2015 IEEE International Symposium on PerformanceAnalysis of Systems and Software (ISPASS), pages 225–234, March 2015.doi:10.1109/ISPASS.2015.7095808. → page 4[20] X. Ge, H. Jin, and V. C. M. Leung. Opportunistic downlink scheduling withresource-based fairness and feedback reduction in distributed antenna systems. IEEETransactions on Vehicular Technology, 65(7):5007–5021, July 2016. ISSN0018-9545. doi:10.1109/TVT.2015.2453637. → page 3[21] X. Ge, X. Li, H. Jin, J. Cheng, and V. C. M. Leung. Joint user association andscheduling for load balancing in heterogeneous networks. In 2016 IEEE GlobalCommunications Conference (GLOBECOM), pages 1–6, Dec 2016.doi:10.1109/GLOCOM.2016.7841943. → page 3[22] R. Gerber and S. Hong. Slicing real-time programs for enhanced schedulability.ACM Trans. Program. Lang. Syst., 19(3):525–555, May 1997. ISSN 0164-0925.doi:10.1145/256167.256394. URL →pages 19, 20[23] G. Greenspan. Multichain private blockchain-white paper. URl: http://www.multichain. com/download/MultiChain-White-Paper. pdf, 2015. → page 9[24] S. Haber and W. S. Stornetta. How to time-stamp a digital document. Journal ofCryptology, 3(2):99–111, Jan 1991. ISSN 1432-1378. doi:10.1007/BF00196791.URL → page 6[25] E. IO. Eos. io technical white paper. EOS. IO (accessed 18 December 2017)https://github. com/EOSIO/Documentation, 2017. → page 9[26] M. Jakobsson and A. Juels. Proofs of Work and Bread Pudding Protocols(ExtendedAbstract), pages 258–272. Springer US, 1999. ISBN 978-0-387-35568-9.doi:10.1007/978-0-387-35568-9 18. URL 18. → page 40[27] Jakub Cech. The july 9, 2018 iota snapshot., 2018. Online.→ page 84[28] A. B. Kahn. Topological sorting of large networks. Commun. ACM, 5(11):558–562,Nov. 1962. ISSN 0001-0782. doi:10.1145/368996.369025. URL → page 71[29] H. Kellerer, U. Pferschy, and D. Pisinger. Introduction to NP-Completeness ofKnapsack Problems, pages 483–493. Springer Berlin Heidelberg, 2004. ISBN91978-3-540-24777-7. doi:10.1007/978-3-540-24777-7 16. URL 16. → pages 24, 47[30] S. King and S. Nadal. Ppcoin: peer-to-peer crypto-currency with proof-of-stake(2012). URL https://peercoin. net/assets/paper/peercoin-paper. pdf.[Online], 2017.→ page 8[31] L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACMTrans. Program. Lang. Syst., 4(3):382–401, July 1982. ISSN 0164-0925.doi:10.1145/357172.357176. URL →page 6[32] S. Lee. Explaining directed acylic graph (dag), the real blockchain 3.0, Jan 2018. →page 11[33] C. LeMahieu. Nano: A feeless distributed cryptocurrency network. URL:https://nano. org/en/whitepaper, 2018. → pages 11, 62[34] S. D. Lerner. Dagcoin: a cryptocurrency without blocks, 2015. → page 11[35] MATLAB., 2017. → pages25, 47, 48[36] F. Mehmeti and T. Spyropoulos. Is it worth to be patient? analysis and optimizationof delayed mobile data offloading. In IEEE INFOCOM 2014 - IEEE Conference onComputer Communications, pages 2364–2372, April 2014.doi:10.1109/INFOCOM.2014.6848181. → page 3[37] R. C. Merkle. Protocols for public key cryptosystems. In 1980 IEEE Symposium onSecurity and Privacy, pages 122–122, April 1980. doi:10.1109/SP.1980.10006. →page 6[38] R. C. Merkle. A Digital Signature Based on a Conventional Encryption Function,pages 369–378. Springer Berlin Heidelberg, 1988. ISBN 978-3-540-48184-3.doi:10.1007/3-540-48184-2 32. URL 32. →page 38[39] S. Nakamoto. Bitcoin: A peer-to-peer electronic cash system. White Paper:, 2008. → page 7[40] J. R. Norris. Markov Chains. Cambridge Series in Statistical and ProbabilisticMathematics. Cambridge University Press, 1997. doi:10.1017/CBO9780511810633.→ page 1792[41] PlayStation Now., 2017. Online. → page 14[42] S. Popov. The tangle. cit. on, page 131, 2016. → pages 11, 62, 72, 76, 78[43] M.-R. Ra, J. Paek, A. B. Sharma, R. Govindan, M. H. Krieger, and M. J. Neely.Energy-delay tradeoffs in smartphone applications. In Proceedings of the 8thInternational Conference on Mobile Systems, Applications, and Services, MobiSys’10, pages 255–270. ACM, 2010. ISBN 978-1-60558-985-5.doi:10.1145/1814433.1814459. URL→ page 3[44] A. Rosic. Proof of work vs proof of stake: Basic mining guide, October 2017. → page 61[45] J. Scott, R. Gass, J. Crowcroft, P. Hui, C. Diot, and A. Chaintreau. CRAWDADdataset cambridge/haggle (v. 2006-09-15). Downloaded from, Sept. 2006. traceset: imote.→ page 51[46] C. Shi, M. H. Ammar, E. W. Zegura, and M. Naik. Computing in cirrus clouds: Thechallenge of intermittent connectivity. In Proceedings of the First Edition of theMCC Workshop on Mobile Cloud Computing, MCC ’12, pages 23–28. ACM, 2012.ISBN 978-1-4503-1519-7. doi:10.1145/2342509.2342515. URL → page 16[47] C. Shi, V. Lakafosis, M. H. Ammar, and E. W. Zegura. Serendipity: Enabling remotecomputing among intermittently connected mobile devices. In Proceedings of theThirteenth ACM International Symposium on Mobile Ad Hoc Networking andComputing, MobiHoc ’12, pages 145–154. ACM, 2012. ISBN 978-1-4503-1281-3.doi:10.1145/2248371.2248394. URL→ pages 4, 16[48] Y.-M. Tai and Y.-C. Ku. Will stock investors use mobile stock trading? a benefit-riskassessment based on a modified utaut model. Journal of Electronic CommerceResearch, 14(1):67–84, 2013. URL → page 14[49] Z. Wang, H. Shah-Mansouri, and V. Wong. How to download more data fromneighbors? a metric for d2d data offloading opportunity. IEEE Transactions onMobile Computing, PP(99):1–1, 2016. ISSN 1536-1233.doi:10.1109/TMC.2016.2604260. → page 5[50] Y. Yang. A polynomial arc-search interior-point algorithm for linear programming.Journal of Optimization Theory and Applications, 158(3):859–873, Sep 2013. ISSN931573-2878. doi:10.1007/s10957-013-0281-0. URL → pages 25, 48[51] S. Yi, C. Li, and Q. Li. A survey of fog computing: Concepts, applications andissues. In Proceedings of the 2015 Workshop on Mobile Big Data, Mobidata ’15,pages 37–42. ACM, 2015. ISBN 978-1-4503-3524-9.doi:10.1145/2757384.2757397. URL→ pages 3, 1494


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items