From f7c28b099f928cc6fb48fc9cc072656d8c3bb902 Mon Sep 17 00:00:00 2001 From: Harald Welte Date: Mon, 21 Dec 2009 13:30:17 +0100 Subject: [handover] Real handover algorithm This implements the handover algorithm (and associated parameters) as described in Chapter 8 of the book "Performance Enhancements in a Frequency |Hopping GSM Network" by Thomas Toftegard Nielsen and Jeroen Wigard. The parameters such as averaging windows are configured in struct gsm_network. We keep some state to trakc up to 10 neighbors as they are being reported from the MS. This has so far only been tested in a network with two BTS that have each other as neighbor. Networks with morge neighbors might encounter bugs. --- openbsc/include/openbsc/gsm_data.h | 30 +++++ openbsc/src/chan_alloc.c | 2 + openbsc/src/gsm_04_08.c | 1 + openbsc/src/gsm_data.c | 8 ++ openbsc/src/handover_decision.c | 227 ++++++++++++++++++++++++++++++++----- 5 files changed, 241 insertions(+), 27 deletions(-) (limited to 'openbsc') diff --git a/openbsc/include/openbsc/gsm_data.h b/openbsc/include/openbsc/gsm_data.h index d19f38bc1..876955824 100644 --- a/openbsc/include/openbsc/gsm_data.h +++ b/openbsc/include/openbsc/gsm_data.h @@ -143,6 +143,20 @@ struct gsm_loc_updating_operation { unsigned int waiting_for_imei : 1; }; +/* Maximum number of neighbor cells whose average we track */ +#define MAX_NEIGH_MEAS 10 +/* Maximum size of the averaging window for neighbor cells */ +#define MAX_WIN_NEIGH_AVG 10 + +/* processed neighbor measurements for one cell */ +struct neigh_meas_proc { + u_int16_t arfcn; + u_int8_t bsic; + u_int8_t rxlev[MAX_WIN_NEIGH_AVG]; + unsigned int rxlev_cnt; + u_int8_t last_seen_nr; +}; + #define MAX_A5_KEY_LEN (128/8) #define RSL_ENC_ALG_A5(x) (x+1) @@ -207,6 +221,9 @@ struct gsm_lchan { struct gsm_meas_rep meas_rep[6]; int meas_rep_idx; + /* table of neighbor cell measurements */ + struct neigh_meas_proc neigh_meas[MAX_NEIGH_MEAS]; + struct { u_int32_t bound_ip; u_int32_t connect_ip; @@ -463,6 +480,19 @@ struct gsm_network { int send_mm_info; struct { int active; + /* Window RXLEV averaging */ + unsigned int win_rxlev_avg; /* number of SACCH frames */ + /* Window RXQUAL averaging */ + unsigned int win_rxqual_avg; /* number of SACCH frames */ + /* Window RXLEV neighbouring cells averaging */ + unsigned int win_rxlev_avg_neigh; /* number of SACCH frames */ + + /* how often should we check for power budget HO */ + unsigned int pwr_interval; /* SACCH frames */ + /* how much better does a neighbor cell have to be ? */ + unsigned int pwr_hysteresis; /* dBm */ + /* maximum distacne before we try a handover */ + unsigned int max_distance; /* TA values */ } handover; /* layer 4 */ diff --git a/openbsc/src/chan_alloc.c b/openbsc/src/chan_alloc.c index a23192ae6..c42b60b46 100644 --- a/openbsc/src/chan_alloc.c +++ b/openbsc/src/chan_alloc.c @@ -259,6 +259,8 @@ void lchan_free(struct gsm_lchan *lchan) lchan->meas_rep[i].flags = 0; lchan->meas_rep[i].nr = 0; } + for (i = 0; i < ARRAY_SIZE(lchan->neigh_meas); i++) + lchan->neigh_meas[i].arfcn = 0; /* FIXME: ts_free() the timeslot, if we're the last logical * channel using it */ diff --git a/openbsc/src/gsm_04_08.c b/openbsc/src/gsm_04_08.c index 281982e22..156927f56 100644 --- a/openbsc/src/gsm_04_08.c +++ b/openbsc/src/gsm_04_08.c @@ -1404,6 +1404,7 @@ static int gsm48_rx_mm_imsi_detach_ind(struct msgb *msg) * imagine an IMSI DETACH happening during an active call! */ /* subscriber is detached: should we release lchan? */ + lchan_auto_release(msg->lchan); return 0; } diff --git a/openbsc/src/gsm_data.c b/openbsc/src/gsm_data.c index 94ed91ba5..12f439be2 100644 --- a/openbsc/src/gsm_data.c +++ b/openbsc/src/gsm_data.c @@ -210,6 +210,14 @@ struct gsm_network *gsm_network_init(u_int16_t country_code, u_int16_t network_c net->T3113 = GSM_T3113_DEFAULT; /* FIXME: initialize all other timers! */ + /* default set of handover parameters */ + net->handover.win_rxlev_avg = 10; + net->handover.win_rxqual_avg = 1; + net->handover.win_rxlev_avg_neigh = 10; + net->handover.pwr_interval = 6; + net->handover.pwr_hysteresis = 3; + net->handover.max_distance = 9999; + INIT_LLIST_HEAD(&net->trans_list); INIT_LLIST_HEAD(&net->upqueue); INIT_LLIST_HEAD(&net->bts_list); diff --git a/openbsc/src/handover_decision.c b/openbsc/src/handover_decision.c index 736679ab1..b37cecddb 100644 --- a/openbsc/src/handover_decision.c +++ b/openbsc/src/handover_decision.c @@ -32,7 +32,9 @@ #include #include #include +#include +/* issue handover to a cell identified by ARFCN and BSIC */ static int handover_to_arfcn_bsic(struct gsm_lchan *lchan, u_int16_t arfcn, u_int8_t bsic) { @@ -50,55 +52,226 @@ static int handover_to_arfcn_bsic(struct gsm_lchan *lchan, return bsc_handover_start(lchan, new_bts); } -#define RXLEV_HYST 3 - -/* process an already parsed measurement report */ -static int process_meas_rep(struct gsm_meas_rep *mr) +/* did we get a RXLEV for a given cell in the given report? */ +static int rxlev_for_cell_in_rep(struct gsm_meas_rep *mr, + u_int16_t arfcn, u_int8_t bsic) { - struct gsm_meas_rep_cell *mr_cell = NULL; - unsigned int best_better_db; int i; - /* we currently only do handover for TCH channels */ - switch (mr->lchan->type) { - case GSM_LCHAN_TCH_F: - case GSM_LCHAN_TCH_H: - break; - default: - return 0; + for (i = 0; i < mr->num_cell; i++) { + struct gsm_meas_rep_cell *mrc = &mr->cell[i]; + + /* search for matching report */ + if (!(mrc->arfcn == arfcn && mrc->bsic == bsic)) + continue; + + mrc->flags |= MRC_F_PROCESSED; + return mrc->rxlev; } + return -ENODEV; +} - /* FIXME: implement actual averaging over multiple measurement - * reports */ +/* obtain averaged rxlev for given neighbor */ +static int neigh_meas_avg(struct neigh_meas_proc *nmp, int window) +{ + unsigned int i, idx; + int avg = 0; - if (mr->num_cell > 6) - return 0; + idx = calc_initial_idx(ARRAY_SIZE(nmp->rxlev), + nmp->rxlev_cnt % ARRAY_SIZE(nmp->rxlev), + window); + + for (i = 0; i < window; i++) { + int j = (idx+i) % ARRAY_SIZE(nmp->rxlev); + + avg += nmp->rxlev[j]; + } + + return avg / window; +} + +/* find empty or evict bad neighbor */ +static struct neigh_meas_proc *find_evict_neigh(struct gsm_lchan *lchan) +{ + int j, worst = 999999; + struct neigh_meas_proc *nmp_worst; + + /* first try to find an empty/unused slot */ + for (j = 0; j < ARRAY_SIZE(lchan->neigh_meas); j++) { + struct neigh_meas_proc *nmp = &lchan->neigh_meas[j]; + if (!nmp->arfcn) + return nmp; + } + + /* no empty slot found. evict worst neighbor from list */ + for (j = 0; j < ARRAY_SIZE(lchan->neigh_meas); j++) { + struct neigh_meas_proc *nmp = &lchan->neigh_meas[j]; + int avg = neigh_meas_avg(nmp, MAX_WIN_NEIGH_AVG); + if (avg < worst) { + worst = avg; + nmp_worst = nmp; + } + } + + return nmp_worst; +} + +/* process neighbor cell measurement reports */ +static void process_meas_neigh(struct gsm_meas_rep *mr) +{ + int i, j, idx; + + /* for each reported cell, try to update global state */ + for (j = 0; j < ARRAY_SIZE(mr->lchan->neigh_meas); j++) { + struct neigh_meas_proc *nmp = &mr->lchan->neigh_meas[j]; + unsigned int idx; + int rxlev; + + /* skip unused entries */ + if (!nmp->arfcn) + continue; + + rxlev = rxlev_for_cell_in_rep(mr, nmp->arfcn, nmp->bsic); + idx = nmp->rxlev_cnt % ARRAY_SIZE(nmp->rxlev); + if (rxlev >= 0) { + nmp->rxlev[idx] = rxlev; + nmp->last_seen_nr = mr->nr; + } else + nmp->rxlev[idx] = 0; + nmp->rxlev_cnt++; + } + + /* iterate over list of reported cells, check if we did not + * process all of them */ + for (i = 0; i < mr->num_cell; i++) { + struct gsm_meas_rep_cell *mrc = &mr->cell[i]; + struct neigh_meas_proc *nmp; + + if (mrc->flags & MRC_F_PROCESSED) + continue; + + nmp = find_evict_neigh(mr->lchan); + + nmp->arfcn = mrc->arfcn; + nmp->bsic = mrc->bsic; + + idx = nmp->rxlev_cnt % ARRAY_SIZE(nmp->rxlev); + nmp->rxlev[idx] = mrc->rxlev; + nmp->rxlev_cnt++; + nmp->last_seen_nr = mr->nr; + + mrc->flags |= MRC_F_PROCESSED; + } +} + +/* attempt to do a handover */ +static int attempt_handover(struct gsm_meas_rep *mr) +{ + struct gsm_network *net = mr->lchan->ts->trx->bts->network; + struct neigh_meas_proc *best_cell = NULL; + unsigned int best_better_db = 0; + int i, rc; /* find the best cell in this report that is at least RXLEV_HYST * better than the current serving cell */ - for (i = 0; i < mr->num_cell; i++) { - unsigned int better; - if (mr->cell[i].rxlev < mr->dl.full.rx_lev + RXLEV_HYST) + + for (i = 0; i < ARRAY_SIZE(mr->lchan->neigh_meas); i++) { + struct neigh_meas_proc *nmp = &mr->lchan->neigh_meas[i]; + int avg, better; + + /* skip empty slots */ + if (nmp->arfcn == 0) continue; - better = mr->cell[i].rxlev - mr->dl.full.rx_lev; + /* caculate average rxlev for this cell over the window */ + avg = neigh_meas_avg(nmp, net->handover.win_rxlev_avg_neigh); + + /* check if hysteresis is fulfilled */ + if (avg < mr->dl.full.rx_lev + net->handover.pwr_hysteresis) + continue; + + better = avg - mr->dl.full.rx_lev; if (better > best_better_db) { - mr_cell = &mr->cell[i]; + best_cell = nmp; best_better_db = better; } } - if (!mr_cell) + if (!best_cell) return 0; - LOGP(DHO, LOGL_INFO, "Cell on ARFCN %u is better: ", mr_cell->arfcn); - if (!mr->lchan->ts->trx->bts->network->handover.active) { + LOGP(DHO, LOGL_INFO, "%s: Cell on ARFCN %u is better: ", + gsm_ts_name(mr->lchan->ts), best_cell->arfcn); + if (!net->handover.active) { LOGPC(DHO, LOGL_INFO, "Skipping, Handover disabled\n"); return 0; } - LOGPC(DHO, LOGL_INFO, "Starting handover\n"); - return handover_to_arfcn_bsic(mr->lchan, mr_cell->arfcn, mr_cell->bsic); + rc = handover_to_arfcn_bsic(mr->lchan, best_cell->arfcn, best_cell->bsic); + switch (rc) { + case 0: + LOGPC(DHO, LOGL_INFO, "Starting handover\n"); + break; + case -ENOSPC: + LOGPC(DHO, LOGL_INFO, "No channel available\n"); + break; + case -EBUSY: + LOGPC(DHO, LOGL_INFO, "Handover already active\n"); + break; + default: + LOGPC(DHO, LOGL_ERROR, "Unknown error\n"); + } + return rc; +} + +/* process an already parsed measurement report and decide if we want to + * attempt a handover */ +static int process_meas_rep(struct gsm_meas_rep *mr) +{ + struct gsm_network *net = mr->lchan->ts->trx->bts->network; + int av_rxlev; + + /* we currently only do handover for TCH channels */ + switch (mr->lchan->type) { + case GSM_LCHAN_TCH_F: + case GSM_LCHAN_TCH_H: + break; + default: + return 0; + } + + /* parse actual neighbor cell info */ + if (mr->num_cell > 0 && mr->num_cell < 7) + process_meas_neigh(mr); + + av_rxlev = get_meas_rep_avg(mr->lchan, MEAS_REP_DL_RXLEV_FULL, + net->handover.win_rxlev_avg); + + /* Interference HO */ + if (rxlev2dbm(av_rxlev) > -85 && + meas_rep_n_out_of_m_be(mr->lchan, MEAS_REP_DL_RXQUAL_FULL, + 3, 4, 5)) + return attempt_handover(mr); + + /* Bad Quality */ + if (meas_rep_n_out_of_m_be(mr->lchan, MEAS_REP_DL_RXQUAL_FULL, + 3, 4, 5)) + return attempt_handover(mr); + + /* Low Level */ + if (rxlev2dbm(av_rxlev) <= -110) + return attempt_handover(mr); + + /* Distance */ + if (mr->ms_l1.ta > net->handover.max_distance) + return attempt_handover(mr); + + /* Power Budget AKA Better Cell */ + if ((mr->nr % net->handover.pwr_interval) == 0) + return attempt_handover(mr); + + return 0; + } static int ho_dec_sig_cb(unsigned int subsys, unsigned int signal, -- cgit v1.2.3