School of Science and Technology 科技學院
Electronic and Computer Engineering 電子工程學系
| Student | Lau Hok Yin |
| Programme | Bachelor of Science with Honours in Cyber and Computer Security |
| Supervisor | Dr. Yaru Fu |
| Year | 2021/22 |
This project investigates cache-aware Device-to-Device assisted communications system performance optimization by joint recommendation and cache decision algorithm.
In a D2D-enabled wireless caching system, popular materials can be actively cached by the mobile user and exchanged directly with each other over the D2D communication link, eliminating the requirement for a helper base station (BS). However, each user’s cache capacity is restricted. The content requested by the user may not always be available in the user’s storage or other users’ storage in the same D2D area. It might lead to higher transmit power consumption, lower data speeds, and longer communication delays. Therefore, system performance optimization is essential.
Cache hit ratio is a measure that determines whether a user may successfully request the item they are looking for. Maximizing the cache hit ratio optimizes system performance by saving system resources and the time required for transmission. Calculating the cache hit ratio involves the cache policies of the user and the recommendation policies, which will be explained in the report to maximize the cache hit ratio.
In this report, we would examine the D2D system’s operating process to identify and explain the portions that might be improved. In addition, we would identify the most suitable methodologies for this project from the previous literature. Joint recommendations and cache decisions would be used to maximize the cache hit ratio for system optimization. The main idea of the method is swap-then-compare. Finally, the problem will be simulated using Monte Carlo methods, and the results will be analyzed using different baselines.
The project includes several key goals that should be met, and this session would outline all the goals that must be met throughout the course of the project, as well as briefly discuss the steps that would be done to reach each goal and what each goal entails.
The theme of this project is the performance optimization of cache aware D2D communication system, in order to achieve the performance optimization, we need to solve the problem of maximizing the cache hit ratio.
First, the background of this problem should be analyzed, such as the operation principle of the D2D system. Understand the problem background and related concepts in order to propose a solution to the project topic.
In addition, past literature must be studied to understand what factors have been considered in the past on related issues, to find out what can be improved and what can be referred to in this project. Define the difference between this project and the previous studies. Previous literature describes on D2D systems and caching systems to identify various indicators that can affect the performance of the system and ways to improve it. Finally, explain why the optimization problem will be NP-hard level by related literature.
In the solution design we define the system model, identify and explain the elements that need to be considered to maximize the cache hit rate, explain the significance of recommendation and cache placement for this project, and finally combine the two problems and maximize the cache hit rate in a swap then compare fashion.
In the section of experiments and results, the steps to simulate the above algorithm using Monte Carlo method would be show and explain, then compare and analyze the results according to different baselines.
The most important goal that must be achieved is the theme of this project, to optimize the performance of the Cache-aware D2D assisted communication system. To perform performance optimization, it is necessary to understand some important definitions such as cache hit ratio. The first goal to be achieved is to study and explore the background of this project. Only with a deep understanding of the principles of the project, we can analyze the existing situation, discover the existing areas for improvement, and make improvements to the defective areas to achieve performance optimization. Other objectives to be achieved include modeling the social relationships between each user, calculating the set of possible users for a typical user, and problem formulation based on factors such as the distribution of user preferences. Problem formulation is one of the most important objectives to be achieved.
This objective is to present mathematically the various factors in the research topic, including user preferences, user relationships, and factors that affect the user’s decision to transfer data, and to define each of these factors in mathematical form, and finally to perform the formulation. Another goal that needs to be achieved is to propose a solution based on the formulation, i.e., a way to optimize the performance of the main idea of the solution. The objective of the final, simulation is to offer evidence to establish that the findings of this study are viable, as well as data.
The primary purpose of this project is to optimize the system, and to do so, we strive to maximize the cache hit rate.
The research methodology of this project is divided into four main parts, the first part is to search the project background and relevant references, such as past literature. This section has previously been discussed in chapters 1 and 2. Secondly, the problem formulation is carried out to express the problem in mathematical form. This chapter would describe the part of problem formulation, then propose a solution and design algorithm for the result of the problem formulation. Finally, we use octave to perform simulation to support the results of the above steps.
Background and reference section, this section is mainly to find and understand in depth the
definition of various concepts related to the problem, such as D2D model and D2D helper set,
user preference distribution and user relationship, etc.
The problem formulation part is mainly to find and define the goals and constraints of the
project through mathematical equations. The main goal of this section is to maximize the cache hit ratio of D2D enabled wireless caching networks, since cache hit ratio is an important factor that affects the performance of the d2d caching system. In the problem formulation step, user requirements and preferences would be defined.
The solution section would draw conclusions based on the theories presented in the
background section and the problem formulation section, and then propose a specific solution
to the problem and explain it in-depth, explaining the rationale and feasibility of the method
found through this project.
The final part of the simulation would use OCTAVE to demonstrate the feasibility of the project using actual experimental results and data.
In this section, we define the system model and explain how the system model work. Important objectives have been defined for the formulation. This section mainly focuses on the
experimental methods and preparatory work before the implementation.
The formulation steps are as follows:
To formulate the problem, we must first define a system model for the D2D communication system. The model of a caching system should consider user preferences and recommendation decisions.
Figure 1. System Model
Before concluding this sub-section, we will summarize how the system model works. The most important thing in this system is the connection between Cloud server and MBS, when users can’t get the requested content in the D2D area, they need to get the content from cloud server through MBS and backhaul link. There are different users in the D2D area, and each user has their own storage space with different content stored in it, and the size of the storage is limited. When users want to get other content, they will first look for it in their own storage. If the content is not available in the user’s storage, the user will send a request to the D2D area through the D2D link, and if the content is not available in the area, the request will be sent to the MBS to get the content from the cloud server.
This chapter will mention all the milestones we have achieved and the dates of their completion and present the differences between the plan and the reality to bring out the difficulties encountered while carrying out the project. In this section we will focus on the simulation steps using the joint algorithm and analyze the system performance.
In this project we have completed a background understanding of the concepts related to cache systems and D2D systems, and we have learned what factors affect the performance of the system. By understanding the project, we decided to optimize performance by maximizing cache hit ratio. Another milestone is to understand the difficulty of this project and what are the feasible approaches through the past literature, and to investigate the concept of simulation approach. After completing the above work, we started to work on the next milestone, the methodology of the project. We started our plan to maximize the cache hit ratio by defining different values such as user preference distribution. We know the equation for maximizing the cache hit ratio from previous literature, which will be used in the simulation part. After defining the values required for maximization, we design a swap-and-compare algorithm to calculate the cache decision and recommendation decision respectively by referring to the previous literature, and finally, these two algorithms will be used as part of the joint algorithm. We derive the joint algorithm for the cache policy and recommendation policy. The last milestone is to simulate the above algorithms and analyze whether the algorithms are effective in improving the system performance by simulating the performance.
The background research and the study of the past literature were successfully completed by December 2021, and the methodology and solution were successfully completed by April 2022, although not by February 2022 as planned. The simulation part was carried out in April and May 2022, and difficulties were encountered in running the joint algorithm along the way, and the simulation part was solved in May.
This subsection describes the steps to perform a simulation using the joint optimization algorithm.
After studying the caching policy under the given recommendation policy and the recommendation policy under the given caching policy, we design a joint algorithm based on the above study:
In the joint algorithm, we would use the given recommendation policy to obtain the caching policy by caching algorithm. Then use the acquired caching policy to update the target recommendation policy by recommendation. It will stop only when the maximum CHR or literation number is reached.
About the steps to perform a simulation using the joint optimization algorithm, we need to first calculate a basic CHR using the algorithms mentioned above and some self-defined data such as the number of users. We need to list all the values needed to calculate the CHR, or equations that can derive the value, and then reapply these values when running the caching and recommendation algorithms, calculating what the CHR of each of the caching and recommendation algorithms is. Finally, this value is used in the joint algorithm to evaluate the system performance. We have run the joint algorithm on Octave and produced a graph that allows us to evaluate the performance of the system, as described in Chapter 5. The algorithm of different baseline will also run for compare.
Figure 2. Joint recommendation and caching algorithms
In this section, we simulated the above-mentioned solutions, i.e., joint recommendation and cache decision algorithms, using all the data needed to maximize the cache hit ratio. A high cache hit ratio means that the user rarely needs to get the content through the base station and the core network, so a high cache hit ratio can reduce the system burden, so the sample transfer time which can improve the system performance. We demonstrate that our algorithm is effective in optimizing system performance by comparing the performance of our algorithm with other possible scenarios through simulations. This will involve the cache capacity budget, and we can use the simulation results to know the impact between different budgets and cache hit ratio, so that we can help users to set the budget.
In this simulation, we will use Octave. When we use Octave to simulate the above algorithm, there are some values that are necessary for the calculation, such as the number of users and the number of contents in the system, we must first define the appropriate values for the required data according to the system model. In the system model, we can see that the system is composed of different D2D areas, in which users exchange data through d2d communication links. In this simulation, the distance of the d2d communication link is 20 M. The number of users in the d2d area will be 10, and each user will have the same cache capacity. The content exchanged by users in the d2d area is based on different topic categories, so the number of theme and content must also be defined. In this simulation, the number of topics will be set to 5 and the number of contents will be set to 30.
The following graph is used to express the cache hit ratio of our proposed joint algorithm for different numbers of iterations, and this graph can be used to evaluate the performance of the algorithm. We tested the cache hit ratio of different capacity budgets for different number of iterations with social aware value is 0.02 and 0.05.
Figure 3. Social aware value = 0.02
Figure 4. Social aware value = 0.05
In the simulation, we set three fixed capacity budgets, the blue line represents a capacity budget of 5, the orange line represents a capacity budget of 3, and the yellow line represents a budget of 1. The social awareness value will be set to different numbers, and the social awareness value is calculated using different distances and different preference associations. In our simulation, the maximum social awareness value will be 1. A larger social aware value means that the users are closer to each other, and their preferences are more related to each other. In a graph with social aware value set to 0.02, the highest cache hit ratio will be 14, and this value is based on a capacity budget of 5. In the case where the social awareness value is 0.05 and the capacity budget is also 5, the cache hit ratio of this simulation is 10, which is lower than the case where the social awareness value is 0.02. Also, we can see in the graph that the blue line always has a higher cache hit ratio, while the orange line is always in the middle and the yellow line is always the lowest.
From the above results we can see that a higher capacity will result in a higher cache hit ratio. Also, the cache hit ratio is higher when the social awareness value is lower.
After showing the performance of the algorithm, we will compare the algorithm with some criteria, including different recommended policies and different cache policies. We will combine these policies with each other to form a baseline that can be used to compare the cache hit ratio under different scenarios and determine whether the algorithm performs at the level we expect.
Before we begin examining the graph, let’s consider the significance of the baseline we established. Different baselines represent different caching policies and recommendation policies. In baseline 1, the caching decision will cache the most interesting content to the user according to the user’s own preference until the user’s cache capacity is full. The recommendation policy in baseline 1 will also recommend the most interesting content to users. The caching policies and recommendation strategy of baseline 1 are both dependent on user preferences.
Baseline 2 caches the content that users are most interested in depending on their preferences until their cache capacity is filled. The main difference between baseline 1 and baseline 2 is that in baseline 2, no content will be recommended by the recommendation policy. Baseline 2 will not recommend any content to users.
Baseline 3 will cache the content based on the preferences of all users until the user’s cache capacity is filled up. Since the cache is based on the preferences of all users, all users will cache the same content. The recommendation policy will same as the baseline 1, recommends the most interesting content to users.
The main difference between the three baselines is the difference between caching based on individual user preferences and caching based on the preferences of all users, and the difference between caching with and without recommendations.
This graph will show the cache capacity budget and cache hit ratio of users for different baselines and algorithms we designed. In this chart, we can clearly see the performance gap between our designed algorithms and various standards. We will simulate the social awareness value at 0.01 and 0.04. The social awareness value is set in the same way as the previous graph, and we choose two reasonable numbers within one. The objective for selecting two values in the simulation is to evaluate how the social aware value influences the algorithm’s performance.
Figure 5. Social aware value = 0.01
Figure 6. Social aware value = 0.04
The graphs show that our proposed algorithm in this project performs the best regardless of the social awareness value, and our algorithm always obtains the highest cache hit ratio. When the social awareness value is 0.01, even if the capacity budget is only 1, our algorithm achieves a cache hit ratio of 11, which is the same as the cache hit ratio in the case of baseline 2 using the maximum capacity budget. The cache hit ratio of our algorithm with lowest capacity budget is higher than the cache hit ratio of baseline 3 at the highest budget, which is only 7 at a capacity budget of 7. Comparing with baseline1, the cache hit ratio of our algorithm is always higher than that of baseline 1 for the same capacity budget. With a social awareness value of 0.04, our algorithm’s cache hit ratio outperforms all baselines with the same capacity budget. At the lowest budget, the cache hit ratio of our algorithm is 8, the cache hit ratio of baseline 1 is 5, the cache hit ratio of baseline 2 is 4, and the cache hit ratio of baseline 3 is 3.
On the other hand, regardless of the social aware value, baseline1 always performs the best and baseline3 always performs the worst without including the algorithms we provide. baseline1’s caching strategy and recommendation strategy are based on users’ personal preferences. In baseline3, the caching policy is based on the preferences of all users, while the recommendation policy is based on the personal preferences of users. Therefore, we can speculate that the performance of the caching policy based on all users’ preferences will be worse than the caching policy based on users’ own preferences, because the preferences of all users may be very different from the users’ own preferences, and caching based on all users’ preferences may prevent some recommended contents from being cached based on users’ preferences.
The graph above demonstrates once again that the bigger the cache capacity budget, the higher the cache hit ratio. This is because higher budget can reduce the situation of not being able to cache the content due to lack of storage space. With higher capacity budget, users can cache more content, and on the other hand, more content is cached successfully, so the cache hit ratio is affected by the capacity budget. In the above graph we can see that our joint algorithm performs better than the algorithm using other recommendation and caching policies, which proves that our algorithm helps to optimize the system performance to some extent.
The goal of this project is to optimize the performance of the cache aware device-to-device assisted communication system. The most intuitive manifestation of the performance optimization of this system is that when a user requests a content, the user can successfully get the content in his D2D area without spending extra time and cost to refer the request to the base station, which can be achieved by improving the cache hit ratio.
The main contribution of this project is to investigate the joint recommendation decision and cache decision algorithms to improve the cache hit ratio, and to simulate the correlation between cache hit ratio and capacity budget, where higher capacity budget leads to higher cache hit ratio. The cache hit ratio is also shown to increase with lower social awareness value. Simulation results compared with different baselines demonstrate that the joint algorithm we studied can optimize the system performance. In this project, we design the cache placement for each user by studying the caching algorithm and find the best capacity budget for each user through the simulation process.
In this project, we believe that the optimal decision method is to optimize the cache decision and recommendation decision. Since the difficulty of the cache decision and recommendation decision optimization problem is NP hardness, we will combine the two problems. We study joint caching decision and recommendation decision algorithms to study the solution on a given decision, which we consider as the suboptimal decision.
When optimizing the performance of a network, there are many metrics that can be considered besides cache hit ratio, including throughput, energy efficiency, and latency. Performance optimization that takes into account these metrics will be the next item to consider.
Jonathan handles all external affairs include business development, patents write up and public relations. He is frequently interviewed by media and is considered a pioneer in 3D printing products.
After graduating from OUHK, Krutz obtained an M.Sc. in Engineering Management from CityU. He is now completing his second master degree, M.Sc. in Biomedical Engineering, at CUHK. Krutz has a wide range of working experience. He has been with Siemens, VTech, and PCCW.
Hugo Leung Wai-yin, who graduated from his four-year programme in 2015, won the Best Paper Award for his ‘intelligent pill-dispenser’ design at the Institute of Electrical and Electronics Engineering’s International Conference on Consumer Electronics – China 2015.
The pill-dispenser alerts patients via sound and LED flashes to pre-set dosage and time intervals. Unlike units currently on the market, Hugo’s design connects to any mobile phone globally. In explaining how it works, he said: ‘There are three layers in the portable pillbox. The lowest level is a controller with various devices which can be connected to mobile phones in remote locations. Patients are alerted by a sound alarm and flashes. Should they fail to follow their prescribed regime, data can be sent via SMS to relatives and friends for follow up.’ The pill-dispenser has four medicine slots, plus a back-up with a LED alert, topped by a 500ml water bottle. It took Hugo three months of research and coding to complete his design, but he feels it was worth all his time and effort.
Hugo’s public examination results were disappointing and he was at a loss about his future before enrolling at the OUHK, which he now realizes was a major turning point in his life. He is grateful for the OUHK’s learning environment, its industry links and the positive guidance and encouragement from his teachers. The University is now exploring the commercial potential of his design with a pharmaceutical company. He hopes that this will benefit the elderly and chronically ill, as well as the society at large.
Soon after completing his studies, Hugo joined an automation technology company as an assistant engineer. He is responsible for the design and development of automation devices. The target is to minimize human labor and increase the quality of products. He is developing products which are used in various sections, including healthcare, manufacturing and consumer electronics.
| Course Code | Title | Credits | |
|---|---|---|---|
| COMP S321F | Advanced Database and Data Warehousing | 5 | |
| COMP S333F | Advanced Programming and AI Algorithms | 5 | |
| COMP S351F | Software Project Management | 5 | |
| COMP S362F | Concurrent and Network Programming | 5 | |
| COMP S363F | Distributed Systems and Parallel Computing | 5 | |
| COMP S382F | Data Mining and Analytics | 5 | |
| COMP S390F | Creative Programming for Games | 5 | |
| COMP S492F | Machine Learning | 5 | |
| ELEC S305F | Computer Networking | 5 | |
| ELEC S348F | IOT Security | 5 | |
| ELEC S371F | Digital Forensics | 5 | |
| ELEC S431F | Blockchain Technologies | 5 | |
| ELEC S425F | Computer and Network Security | 5 |
| Course Code | Title | Credits | |
|---|---|---|---|
| ELEC S201F | Basic Electronics | 5 | |
| IT S290F | Human Computer Interaction & User Experience Design | 5 | |
| STAT S251F | Statistical Data Analysis | 5 |
| Course Code | Title | Credits | |
|---|---|---|---|
| COMPS333F | Advanced Programming and AI Algorithms | 5 | |
| COMPS362F | Concurrent and Network Programming | 5 | |
| COMPS363F | Distributed Systems and Parallel Computing | 5 | |
| COMPS380F | Web Applications: Design and Development | 5 | |
| COMPS381F | Server-side Technologies and Cloud Computing | 5 | |
| COMPS382F | Data Mining and Analytics | 5 | |
| COMPS390F | Creative Programming for Games | 5 | |
| COMPS413F | Application Design and Development for Mobile Devices | 5 | |
| COMPS492F | Machine Learning | 5 | |
| ELECS305F | Computer Networking | 5 | |
| ELECS363F | Advanced Computer Design | 5 | |
| ELECS425F | Computer and Network Security | 5 |
