有幸在斯德哥尔摩的T-Centralen的World Trade Center参加了Huawei Sweden Hackthon 2022，即使是作为一支入围水队也收获了宝贵的经验。
比赛体验是相当不错，有自助晚餐、早餐和午餐披萨供应，以及自主的茶水、水果等；不过由于时间非常长（1个晚上+1个上午），同时如果无法有效优化、求解的话则毫无进展，所以过程依然相当煎熬。
题目描述
Background Description
- Many users connected to a base station need to send and receive data in real-time.
- As we have limited bandwidth, efficient allocation of data channel resources to the users has a significant impact on the quality of experience of the users.
- Here, we focus on the simplified version of the downlink data channel allocation problem as a key building block of mobile networks.
- 5G massive MIMO resources can be divided into M*N grids where in each grid only a single user can be placed.
- We can have multiple instances of each user based on the size of its data. A user with bigger size of data potentially needs more instances (more grids) to send its data. For example, in the following figure, we have 5 instances of user U1, 3 instances of U2 and 2 instances of U3.
- We cannot place more than one instance of the same user in the same column, for example, two U1s cannot be placed in the same column. But we can have multiple instances of the same user in the same row.
\(M\): Number of rows
\(N\): Number of Columns
\(U\): Set of users, {U1, U2, …}
\(|U|\): Number of users
Problem statement
Each user is denoted by a tuple including: {initial speed, data size, factor}
Initial speed: the speed of sending the user’s data when there is no conflict with other users
Data size: the total amount of data that the user wants to send.
Factor: the factor by which the data speed of the user reduces as a result of collocating with other users in the same column.
For example, we can have three users as follows:
U1={20, 5000,0.3}, This means that user U1 wants to send 5000 bytes data and if there is no conflict with other users the data will be sent by speed 20.
U2={15,3500,0.25},
U3={26,4200,0.6}
The number of instances of each user depends on both the size of its data and the speed. When a user’s data cannot be sent entirely in a single grid, it needs multiple grids.
Users placed in the same column negatively affect each other in terms of data speed, while users on the same row have no effect on each other.
The speed of each user in case of not collocating with other users is equal to its initial speed, however, in case of collocating with other users in the same column, it is reduced to
\[Speed_i=initial\_{Speed}_i \times \left( 1- collocated\_{factor}_i \right) \]Where:
\[ collocated\_{factor}_i = factor_i \times \sum_{\forall j\neq i} factor_j \]which Users \(j\) are assianed to the same column.
Note 1: The speed cannot be zero. Thus, if \(Speed_i\) leads to a negative value (i.e., the collocated factor gets bigger than 1), consider the speed equal to zero.
For a single column and three users, we can have four different scenarios where the users speeds are calculated as follows:
Mapping speed to data transmission rate
There is a corresponding relationship between the speed and the amount of data that a user can send, shown by the speed to data map table. Here is an example of such a table.
For example, when the speed of a user is 8, 2158 bytes data can be sent.
Notes: To map the speed to data, use the given F function than rounds the speed considering the floating point error. For example, if the speed U1 collocated with U2 is 10.65, its data is 2696.
Note 2: the F function is not exactly the same as the know round function because it may roundup a number which is extremly close to the next integer number to avoid the effect of floating point error, for example if the speed is 12.999999, F functions returns 13 rather than 12.
For the example in the previous slide, the data sent by each user, in each scenario is calculated as follows:
U1={20, 5000,0.3}, U2={15,3500,0.25}, U3={26,4200,0.6}
Objective and Constraints
Objective: Maximise the sum of average speed of all users (\(Avg\_Speed_i\)), formulated as
\[ Objective\_function= \frac{\sum_{\forall Users} Avg\_Speed_i}{BestSpeedUsers} \]Where \(BestSpeedUsers\) is sum of maximum speed of all users and can be calculated by \(\sum_{\forall Users} Init\_{Speed}_i\)
Indeed objective function is a float number between 0 and 1
Constraint: More than one instance of the same user cannot be placed in the same column.
Penalty term: As we would like to send all the data, we apply a penalty term that shows which portion of total data of all users cannot be sent (
标签：Hackthon,users,speed,sum,Huawei,ij,user,2022,data From： https://www.cnblogs.com/jjmg/p/HuaweiSwedenHackathon2022.html