Patent Document ID: 8965383
Application ID: 13687368
Patent Flag: 1

Claim One:
1. A load balancing method, comprising: constructing a bipartite graph for mobile hosts and capacity slots of base stations, wherein a number of the capacity slots of a base station is equal to a number of the mobile hosts the base station supports, and in the bipartite graph, there is a line between a mobile host and every capacity slot of the base station covering the mobile host; setting a weight for each line in the bipartite graph, wherein all lines from same capacity slot have same weight, and for one base station, lines from the capacity slots of the one base station have weights in an ascending order; converting the bipartite graph into a cost matrix, wherein in the cost matrix, rows and columns represent the capacity slots and the mobile hosts, respectively, a number of the rows is equal to a number of the columns, and each entry represents a weight between the capacity slot and the mobile host; and matching each mobile host with one capacity slot by applying a Hungarian algorithm on the cost matrix, wherein matching the each mobile host with the one capacity slot by applying the Hungarian algorithm on the cost matrix comprises: for each row of the cost matrix, finding a first minimal entry and subtracting the first minimal entry from all entries in that row; for each column of the cost matrix, finding a second minimal entry and subtracting the second minimal entry from all entries in that column; drawing straight lines across rows and columns so that all zeros are covered by the straight lines and the number of the straight lines is minimized; and when the number of the straight lines is equal to the size of the cost matrix, matching the each mobile host with the one capacity slot according to resulted cost matrix; otherwise, finding a smallest entry that is not covered by any straight line, subtracting the found smallest entry from each entry that is not covered by the any straight line, adding the found smallest entry to each entry that is covered by both a horizontal straight line and a vertical straight line, and drawing additional straight lines across the rows and the columns so that the all zeros are covered by the straight lines and the number of the straight lines is minimized, until the number of the straight lines is equal to the size of the cost matrix, and then matching the each mobile host with the one capacity slot according to the resulted cost matrix.