在基于蜂窝网的边缘计算环境中,如何部署边缘服务器是一个重要问题。假定有一个5km*5 km的地理区域,每个基站的的覆盖范围是半径R=500m的圆形区域,移动用户在网络中均匀分布。 (1)请问在该网络中最少应该部署多少个基站才能完成无缝覆盖?请给出具体的理论分析和部署算法,然后给出给定部署算法下每个基站所在位置的坐标;(15分) (2)假定边缘服务器需要和基站共站部署(即将边缘服务器放置在基站所在位置的机房中),每个边缘服务器能够容纳不超过3个基站的用户使用,请问应该最少部署多少个边缘服务器才能满足要求?应该将这些边缘服务器分别放在什么位置才比较合理?(提示:考虑课本8.2节边缘服务器部署问题相关算法。)
时间: 2023-06-15 22:05:36 浏览: 61
(1) 在该网络中最少应该部署多少个基站才能完成无缝覆盖?
理论分析:
假设基站的覆盖范围是一个半径为 R 的圆形区域,移动用户在网络中均匀分布。为了实现无缝覆盖,那么每个用户都应该在至少一个基站的覆盖范围内。因此,我们可以将整个区域划分成若干个半径为 2R 的圆形区域,并且每个圆形区域的中心点应该是一个基站的位置。这样,每个用户都可以被覆盖到。
根据这种划分方式,可以将整个区域划分成 25 个圆形区域,每个区域的中心点即为一个基站的位置。因此,至少需要部署 25 个基站才能完成无缝覆盖。
部署算法:
为了实现无缝覆盖,我们可以将整个区域划分成若干个半径为 2R 的圆形区域,并且每个圆形区域的中心点应该是一个基站的位置。具体的部署算法如下:
1. 将整个区域划分成若干个半径为 2R 的圆形区域;
2. 对于每个圆形区域,选择一个距离该区域中心最近的未被覆盖的点作为基站的位置;
3. 直到所有的圆形区域都被至少一个基站覆盖。
给定部署算法下每个基站所在位置的坐标:
假设整个区域的左下角坐标为 (0,0),那么根据上述部署算法,可以得到每个基站的坐标如下所示:
(500, 500), (1500, 500), (2500, 500), (3500, 500), (4500, 500),
(500, 1500), (1500, 1500), (2500, 1500), (3500, 1500), (4500, 1500),
(500, 2500), (1500, 2500), (2500, 2500), (3500, 2500), (4500, 2500),
(500, 3500), (1500, 3500), (2500, 3500), (3500, 3500), (4500, 3500),
(500, 4500), (1500, 4500), (2500, 4500), (3500, 4500), (4500, 4500)
(2) 应该最少部署多少个边缘服务器才能满足要求?应该将这些边缘服务器分别放在什么位置才比较合理?
根据题目要求,每个边缘服务器能够容纳不超过 3 个基站的用户使用。因此,我们需要将所有的基站分配给不超过 3 个边缘服务器。为了最小化边缘服务器的数量,我们可以使用贪心算法。
具体的部署算法如下:
1. 对所有的基站进行排序,按照距离左下角的距离从小到大排序;
2. 依次将每个基站分配给距离该基站最近的未满载的边缘服务器;
3. 直到所有的基站都被分配。
根据上述部署算法,可以得到最少需要部署 9 个边缘服务器才能满足要求。这些边缘服务器应该放置在以下位置:
(500, 500), (2500, 500), (4500, 500),
(1500, 1500), (3500, 1500),
(500, 2500), (2500, 2500), (4500, 2500),
(1500, 4500)
这些位置可以保证所有的基站都被分配给了不超过 3 个边缘服务器,并且每个边缘服务器的用户负载是相对均衡的。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)