Printer Friendly

El valor de shapley como estrategia de optimizacion de recursos sobre Power Line Communication (PLC).

The value of shapley as a strategy for Resource Optimization on Power Line Communication (PLC)

1 Introduccion

HomePlug AV (HPAV) es uno de los estandares de mayor aceptacion sobre la tecnologia PLC, el cual hace uso de la red electrica como medio fisico de transmision, emplea OFDM (Orthogonal Frequency Division Multiplexing) como tecnica de multiplexacion de la informacion sobre el canal PLC, opera en el rango de 1.8MHz a 28MHz, dividiendo el espectro en 1055 subportadoras, de las cuales solo 917 estan activas para el sistema americano, empleando modulacion adaptativa para cada subportadora dependiendo de las condiciones del canal y hace uso de un Coordinador Central (CCo) el cual esta encargado de realizar la asignacion de recursos y acceso a la red PLC [1]

Teniendo en cuenta que HPAV no cuenta con un mecanismo de optimizacion de recursos adecuado para un entorno multiusuario, el rendimiento de la red disminuye considerablemente a medida que aumenta el numero de nodos que conforman la red PLC [2]. En vista de lo anterior, se propone hacer uso de teoria de juegos cooperativos, soportada en el uso del valor de Shapley, como estrategia para la asignacion de recursos (Bit-rate) a cada uno de los nodos que forman parte de la red PLC, con el fin de mejorar el rendimiento de la red y bajo unas politicas de distribucion claramente definidas.

La teoria de juegos es un area de la matematica propuesta por John Von Neumann en 1928, la cual esta orientada a evaluar las decisiones que puede tomar un individuo al interior de un contexto competitivo de ganancia o perdida, frente a las decisiones que adopten los demas competidores. A este escenario competitivo se le denomina Juego y a los individuos que forman parte de este escenario se les denomina Jugadores [3].

El uso de la teoria de juegos establece tres formas para realizar el modelamiento de un escenario real: extensiva, estrategica y de coalicion. Las dos primeras solo son aplicables a juegos no cooperativos, en donde unicamente prima el interes de cada jugador en obtener el beneficio propio, sin importar el resultado de los demas jugadores. La tercera forma (Coalicion), es aplicable exclusivamente a juegos de tipo cooperativo, el cual corresponde a un juego en el cual dos o mas jugadores no compiten entre si, sino que por el contrario, trabajan de manera conjunta para conseguir el mismo objetivo y por lo tanto, ganan o pierden como un grupo [4]. Adicionalmente, el hecho de trabajar cooperativamente o de establecer coaliciones entre dos o mas jugadores, aumenta la probabilidad de obtener una ganacia superior frente a la obtenida de actuar individualmente. En un juego cooperativo no es necesario analizar las estrategias de los jugadores como ocurre en los juegos no cooperativos; basta solo con conocer la utilidad que puede obtener cada coalision y el vector pagos asociado a los resultados del juego [5].

Al interior de la teoria de juegos cooperativos en diversas ocasiones se ha planteado la siguiente pregunta: ?como dividir el valor neto de un bien o un recurso entre un conjunto de jugadores de forma equitativa?. El problema adquiere mayor importancia cuando la cantidad a dividir es insuficiente para satisfacer las demandas de cada jugador. En este punto es donde surge el problema conocido como Bancarrota. El problema de bancarrota ha sido ampliamente estudiado en el contexto economico y su analisis presenta dos posibles enfoques: el primero se orienta el juego de bancarrota como un juego de utilidad transferible o como un problema de negociacion [6],[7],[8],[9]. El segundo enfoque obedece al metodo axiomatico, donde las soluciones son caracterizadas en terminos de propiedades [10],[11],[7]. El enfoque que se adoptara en el presente articulo sera el de utilidad transferible.

2 Metodologia

Con la finalidad de abordar los aspectos metodologicos es necesario recurrir a los fundamentos establecidos por la teoria de juegos:

Definicion [5] Un juego cooperativo TU (con utilidad transferible) es un par (N, v) donde N = {1, 2, 3 ... n} es el conjunto de jugadores y v : 2n [flecha diestra] R se denomina funcion caracteristica del juego, con v([fi]) = 0. Se denomina Coalicion a cualquier subconjunto no vacio de N. Para cada coalicion S [subconjunto] N esta asociado un numero v(S) el cual representa el pago que se puede asegurar a los jugadores que forman parte de S, independientemente de lo que hagan los demas jugadores. El valor de una coalicion se puede considerar como la cantidad minima que puede obtener una coalicion si todos los jugadores que forman parte de ella se asocian y juegan en equipo.

Definicion [12]. Un juego de bancarrota esta definido como una terna (N, d, E) donde N = {1, 2, 3 ... n} es el conjunto acreedores, d = {[d.sub.1], [d.sub.2], ..., [d.sub.n]} con [d.sub.i] [mayor que o igual a] 0, [atane a todos] i [elemento de] N es el vector de demandas de los acreedores y E corresponde al valor neto que se debe repartir entre los elementos de N.

Para cada problema de bancarrota (N, d, E) se puede definir un juego cooperativo (N, v). El conjunto de jugadores N sera el mismo conjunto de acreedores o demandantes del problema de bancarrota. El valor de la coalicion S en el juego se define como la propiedad a repartir entre los jugadores que no fue reclamada por los demandantes que no pertenecen a la coalicion S. Sea d(S) = [[suma de].sub.i[elemento de]S] [d.sub.i] la suma de las demandas de todos los acreedores que forman parte de la coalicion d(N \ S) = [[suma de].sub.i[elemento de]N\S] [d.sub.i] la suma de las demandas de todos los acreedores que no forman parte de la coalicion S [13].

Definicion [5] Un juego cooperativo (N, v) es un juego de bancarrota si existe un problema de bancarrota en donde (1):

v(S) = max{0, E - d(N \ S)} [atane a todos] S [subconjunto] N (1)

El valor de cada coalicion v(S) obedece a una valoracion pesimista de lo que esta puede lograr, en donde despues de realizar un proceso de repartir entre los demandantes que no estan en la coalicion, el saldo es asignado a la coalicion S.

Uno de los principales problemas que plantea la teoria de juegos cooperativos TU es como repartir la ganancia total v(N) entre todos los jugadores de manera equitativa y acorde con la participacion individual de cada jugador. Una de las tecnicas mas utilizadas para dar solucion a este problema es el valor de Shapley.

Shapley, analizo durante mucho tiempo los juegos cooperativos y en 1953 propuso el concepto de valor de un juego (N, v) dado para cada jugador i [elemento de] N a traves de la siguiente expresion [14] (2):

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (2)

Este valor es conocido como el valor de Shapley para el jugador i, el cual es determinado de forma exclusiva y apriori, por la funcion caracteristica del juego. El valor de Shapley busca establecer una serie de pagos entre los jugadores de manera tal que se cumplan determinados criterios denominados axiomas, previamente establecidos (eficiencia, simetria, jugador pasivo y aditividad) generando como resultado una unica asignacion de recursos entre los jugadores [15]. El valor de Shapley, puede interpretarse como la contribucion marginal esperada del jugador i o como un promedio de las contribuciones marginales [v(S) - v(S - i)] de dicho jugador a todas las coaliciones no vacias S [elemento de] [2.sup.N], considerando que la coalicion del jugador sea equiprobable en tamano (1 [menor que o igual a] s [menor que o igual a] n) y que todas las coaliciones de tamano S tienen la misma probabilidad [14].

O'Neill [6] demostro que el proceso de repartir en un problema de bancarrota (N, d, E) a traves del metodo de realizacion recursiva coincide con el valor de Shapley. Este aspecto es de vital importancia teniendo en cuenta que para realizar la distribucion de E entre sus acreedores, es necesario establecer una serie de reglas de reparto que establezcan algun criterio de asignacion que siga un razonamiento etico y profesional, las cuales para este caso se estableceran mediante el uso de imputaciones para el juego (N, v).

Una imputacion para un juego (N, v) corresponde a un vector de pagos racional individual [fi](v) [elemento de] [R.sup.n], sobre el cual se realiza el proceso de repartir el monto maximo v(N) entre cada uno de los jugadores. Para que la solucion sea adecuada es necesario que el vector de pagos cumpla con el principio de eficiencia [3], en donde (3):

[suma de (i [elemento de] N)] [fi]i(v) = v(N) (3)

Adicionalmente, debe cumplir con el llamado principio de individualidad racional, el cual exige que el pago a cada jugador i sea al menos la cantidad que el jugador puede obtener por si mismo en el juego, es decir (4):

[fi]i(v) [mayor que o igual a] (v{i}) [atane a todos] i [subconjunto o igual a] N (4)

Es posible sugerir que los miembros de cada coalicion reciban un pago total mayor o igual que el valor de esta coalicion, lo cual indica que los pagos seran coalicionalmente razonables. Un vector de pago [fi](v) [elemento de] [R.sup.n] se dice que es racional de grupo si (5):

[suma de (i [elemento de] S)] [[fi].sub.i](v) [mayor que o igual a] v (S) [atane a todos] S [subconjunto o igual a] N (5)

En el momento en el cual se exige a las imputaciones cumplir con el principio de racionalidad para todas las coaliciones, se llega al concepto introducido por Guilles denominado Nucleo [16]. El Nucleo C(v) de un juego (N,v), se define como el conjunto de imputaciones que poseen la propiedad racional de grupo. La expresion que define el nucleo de un juego obedece a la siguiente expresion (6):

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (6)

Shapley [17] introdujo el concepto de coaliciones equilibradas y de juego equilibrado con el fin de establecer las condiciones que determinan si un juego tiene Nucleo vacio o no. Posteriormente demostro que un juego (N, v) esta equilibrado si y solo si el Nucleo no es vacio (C(v) [desigual a] 0).

En vista de lo anterior se propone hacer uso del valor de Shapley como estrategia para repartir de manera equitativa la capacidad disponible en un canal PLC ([BW.sub.T]), bajo un estado de saturacion, entre cada uno de los nodos que forman parte de la red de area local (LAN), soportada en el estandar HomePlug AV (HPAV), el cual hace uso de la red electrica como medio fisico de transmision. Este escenario puede ser representado como un juego TU (N, v), en donde los N nodos seran los jugadores, [d.sub.i] obedece a la capacidad requerida por cada nodo i y E = [BW.sub.T].

3 Pruebas y resultados

3.1 Descripcion del escenario propuesto

En la Figura 1 se presenta el esquema general de la topologia de red propuesta, la cual esta constituida por N nodos. Cada nodo esta conformado por un adaptador PLC y una fuente de trafico. El nodo N sera considerado como nodo principal o Coordinador Central (CCo) de la red PLC, el cual sera el encargado de administrar el Bit-rate asignado a cada nodo (soportado en el valor de Shapley), acorde con las condiciones del canal PLC, el numero de nodos conectados y la demanda de trafico existente.

[FIGURA 1 OMITIR]

Para calcular el valor de BWt se hace uso de la herramienta denominada Generador de Canal PLC (GC_PLC), escrita en MATLAB y desarrollada por el PhD Francisco Javier Canete, perteneciente al Grupo PLC de la Universidad de Malaga - Espana. GC_PLC permite estimar el comportamiento de un canal PLC, acorde con los parametros asociados a la topologia de una red PLC, en un ambiente residencial tipico. Adicionalmente, la herramienta realiza un proceso de evaluacion del canal por debajo de la banda de los 30MHz, considerando el hecho de que los adaptadores de red PLC bajo el estandar HPAV operan en esta banda de frecuencia. En [18] se presenta toda la informacion para el uso de la herramienta GC_PLC.

La expresion para calcular el total de bits/seg que pueden ser transmitidos en el canal PLC, esta dada por (7):

[BW.sub.T] = 1/[T.sub.s] [[N.sub.sp].suma de (k=1)] [log.sub.2] [1 + [SNR.sub.k]/[GAMMA]] (7)

Donde:

[N.sub.sp]: Numero de subportadoras (917).

[T.sub.s]: Tiempo de un simbolo OFDM. ([T.sub.s] = 40.96[micron]) para el caso particular de HPAV.

[SNR.sub.k]: Relacion Senal a Ruido presente en la subportadora k.

[GAMMA]: Se conoce como SNRgap, el cual representa la perdida en SNR en la que se incurre por el hecho de utilizar un esquema de codificacion discreto especifico.

En [19] se sugiere que el valor de [GAMMA] puede ser calculado para efectos practicos mediante (8):

[GAMMA] = 1/1.6 ln [[BER.sub.obj]/0.2] (8)

Donde el [BER.sub.obj], corresponde al BER que se desea sostener. Para el caso particular se considero un valor de [10.sup.-6].

Para el escenario propuesto se ha considerado N = 12 nodos que conforman la red PLC, un canal PLC en estado de saturacion ([BW.sub.T] [mayor que o igual a][[suma de].sup.N.sub.i=1] [d.sub.i]) y un Bit-rate total disponible [BW.sub.T] = E = 159.72 Mbps, el cual ha sido estimado mediante el uso de la herramienta GC_PLC. En la Tabla 1, se encuentra el valor correspondiente al Bit-rate solicitado ([d.sub.i]) por cada nodo i que forma parte de la red PLC. Es importante mencionar que el proceso de optimizacion debe ser realizado para cada periodo HPAV equivalente a dos ciclos de red de la senal de potencia (120V/60Hz) [1], debido a las condiciones dinamicas de trafico y de canal PLC que pueden estar presentes en la red. Para el caso particular, el nodo 12 cumplira la funcion de nodo principal o Coordinador de la red PLC (CCo).

Tal como se menciono anteriormente, se considerara un juego de bancarrota en coherencia con el estado de saturacion del canal PLC, con el fin de calcular el valor de utilidad transferible para cada una de las coaliciones. La rutina elaborada en Matlab para realizar el calculo de cada uno de los valores de utilidad transferible es la siguiente:
Rutina 1. Calcula cada valor de utilidad transferible

% Nj: Numero de Jugadores

% M_Coaliciones: Matriz de coaliciones posibles

% V_Coalicion: Valor de utilidad transferible para cada coalicion

% Rutina para calcular todas las posibles combinaciones

Z=1:1:Nj; %Crea un vector con los numeros consecutivos del 1 a Nj

% Rutina para establecer el numero de coalisiones posibles

n_coal=0;

for i=1:Nj

  n_coal=n_coal+nchoosek(Nj,i);

end

M_Coaliciones=zeros(n_coal,Nj); %Inicializa la matriz de coaliciones
c=0;

for i=1:Nj

    S=nchoosek(Z,i);
    nZ=length(S(:,1));
    for j=1:nZ
      c=c+1;
      Suma_d=0;
      for k=1:i
        Suma_d=Suma_d+V(S(j,k));
        M_Coaliciones(c,k)=S(j,k);
      end

    Suma_dT=BW_T-(Total_V-Suma_d);
    VAux=[0 Suma_dT];
    V_Coalicion(c)=max(VAux);
  end

end


En la Tabla 2, se presenta el valor de utilidad transferible calculado para cada una de las coaliciones v(S) posibles, acorde al escenario propuesto en estado de saturacion, bajo el uso del juego de la bancarrota. Teniendo en cuenta que el numero de jugadores es 12 y el numero de combinaciones posibles seria bastante elevado, solo se registraran en la Tabla los valores correspondientes a v(i) y v(N).

Con base en los valores v(S) registrados en la Tabla 2, es posible establecer cada una de las imputaciones del juego (N, v), teniendo en cuenta que se debe satisfacer el principio de individualidad racional [[fi].sub.i](v) [mayor que o igual a] (vi) [atane a todos]i [elemento de] N y el principio de eficiencia [[suma de].sub.i[elemento de]N] [[fi].sub.i](v) = v(N). Las ecuaciones que describen cada una de las imputaciones para el juego (N, v) son (9):

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (9)

La ecuacion de eficiencia para el escenario propuesto es (10):

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (10)

Con base en las expresiones anteriores, el nucleo del juego seria el siguiente:

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII]. (11)

Para establecer una solucion optima al juego propuesto, se hara uso del valor del Shapley, con el fin de calcular el vector de pesos [fi](v). En la Tabla 3, se presenta la metodologia para calcular cada uno de los valores que forman parte de la matriz de Shapley, acorde con el numero de jugadores, la contribucion por parte de cada una de las coaliciones y la probabilidad P(j); los cuales son necesarios para calcular el valor de Shapley [[fi].sub.i](v) = [[suma de].sub.j[elemento de]N] P(j)[v.sub.i,j] de cada jugador.

La rutina implementada en Matlab para calcular el valor de Shapley [[fi].sub.k](v) [atane a todos] k [elemento de] N es la siguiente:
Rutina 2. Calcula cada valor de Shapley

% Mk_Coaliciones: Matriz de coaliciones asociadas al jugador k
% Vk_Coalicion: Valor de TU para cada coalicion asociada al jugador k
% Sub_coal: Matriz de subcoaliciones conformadas al suprimir el jugador k
% Vk_Sub_coal: Valor de TU para cada subcoalicion
% M_Shapley: Matriz de Shapley
% B: Vector de coeficientes de Shapley (P(j))
% Peso: Vector de valores de Shapley para cada jugador k

% Rutina para identificar Coaliciones acorde al valor de k
for k=1:Nj   %Parametro a consultar en las coaliciones
  for lg=1:Nj   %Numero de elementos en la coalicion
    nMk=0;

    for i=1:n_coal
      for j=1:Nj
        if M_Coaliciones(i,j)==k
          N_ceros=0;
          for g=1:Nj
            if M_Coaliciones(i,g)>0
            N_ceros=N_ceros+1;

          end
       end

%Identifica las coaliciones que cumplen con los parametros de
%longitud lg y jugador k

           if N_ceros==lg
             nMk=nMk+1;
             Mk_Coaliciones(nMk,:)=M_Coaliciones(i,:);
             Vk_Coalicion(nMk)=V_Coalicion(i);
             j=Nj;
           end
         end
       end
     end

% Rutina para identificar las sub-coaliciones
     Sub_coal=zeros(nMk,Nj);
     for i=1:nMk
       j=0;
       for g=1:Nj
         if Mk_Coaliciones(i,g)>0 & Mk_Coaliciones(i,g)~=k
           j=j+1;
           Sub_coal(i,j)=Mk_Coaliciones(i,g);
         end
       end
     end

     %Rutina para identificar valor de sub-coalicion
     for i=1:nMk

     if lg==1
       Vk_Sub_coal(i)=0;
     else
       for j=1:n_coal
         if Sub_coal(i,:)==M_Coaliciones(j,:)
           Vk_Sub_coal(i)=V_Coalicion(j);
         end
       end
     end
   end
   M_Shapley(k,lg)=sum(Vk_Coalicion-Vk_Sub_coal);
   clear Vk_Coalicion;
   clear Vk_Sub_coal;
   clear Mk_Coaliciones;
   clear Sub_coal;
  end
end

% Rutina para calcular los coeficientes Shapley
for S=1:Nj
    B(S)=factorial(S-1)*factorial(Nj-S)/factorial(Nj);

end

%Rutina para calcular los pesos de cada jugador

for i=1:Nj
    Z=M_Shapley(i,:).*B;
    Peso(i)=sum(Z);
end


En la Tabla 4, se presenta el resultado correspondiente a la matriz de Shapley para el escenario propuesto en estado de saturacion. En la ultima columna se observa el valor de Shapley calculado para cada uno de los jugadores, teniendo en cuenta cada uno de los elementos mencionados anteriormente. Adicionalmente se puede apreciar que se cumple [[suma de].sub.(i[elemento de]N)] [[fi].sub.i](v) = v(N) = [BW.sub.T].

En la Tabla 5 se presentan los valores de Bit-rate (BW) correspondientes al BW solicitado y BW asignado para cada nodo, acorde con el valor de Shapley, ante un estado de saturacion y bajo tres condiciones de canal diferentes. Los valores de [BW.sub.T] estimados mediante el uso de GC_PLC son: 159.72Mbps, 120.65Mbps y 83.59Mbps; asociados a las condiciones de canal excelente, regular y deficiente respectivamente.

En la Tabla 5 se observa que el valor de BW asignado es proporcional al BW requerido por cada nodo y adicionalmente, se puede evidenciar que la suma total de los valores asignados corresponde al valor de [Bw.sub.T] respectivo para cada caso, acorde con las condiciones del canal PLC.

3.2 Comparacion de tratamientos BW optimo-PL vs BW-Shapley

Con el fin de evaluar el grado de optimizacion realizado mediante el uso del valor de Shapley, es necesario establecer un metodo alternativo de optimizacion que permita calcular el BW para cada nodo i, y con ello realizar posteriormente un proceso de comparacion de tratamientos. Ante esta situacion se decidio plantear el problema de asignacion de recursos como un problema de Programacion Lineal (PL). En vista de lo anterior, el problema se puede plantear de la siguiente forma (12) (13):

Maximizar [n.suma de (i=1)][x.sub.i] (12)

Sujeto a:

0 [mayor que o igual a] [x.sub.i] [mayor que o igual a] [d.sub.i]

[n-1.suma de (i=1)] [x.sub.i] [menor que o igual a] [BW.sub.T]/2 (13)

[x.sub.n] [menor que o igual a] [n-1.suma de (i=1)] [x.sub.i]

Donde n, [d.sub.i] y [x.sub.i] corresponden al numero de nodos (para el caso particular n = 12), BW solicitado y BW asignado para el nodo i respectivamente. Las restricciones establecidas en el modelo propuesto representan el criterio en el cual la mayoria del trafico circulara a traves del CCo (nodo N), teniendo en cuenta que este nodo es el que permite que el trafico pueda salir hacia internet, por lo tanto, el Bit-rate maximo que podria ser asignado al nodo N([x.sub.n]) seria de [BW.sub.T]/2 .

Para dar solucion al problema de optimizacion se utilizo el Toolbox de Optimizacion incluido en Matlab, el cual permite hacer uso de diversos metodos de optimizacion. Para hacer uso de la herramienta fue necesario organizar la funcion objetivo, las restricciones y el punto inicial de iteracion de forma matricial. Los valores para cada uno de los parametros son los siguientes:

F : Vector de coeficientes de la funcion Objetivo (14):

F = [-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1]; (14)

A, b: Corresponden a las restricciones de desigualdad, en donde A es la matriz de coeficientes y b el vector de resultados para cada una de las inecuaciones (Ax [menor que o igual a] b).

Los valores de BWT para las condiciones de canal excelente, regular y deficiente son: 159.72, 120.65 y 83.59 respectivamente.

[x.sub.0]: Punto inicial para la iteracion (15).

x0 = [000000000000]; (15)

Finalmente, se hace uso de la siguiente expresion (16) con el fin de calcular la solucion al problema planteado:

[x, fval] = linprog(F, A, b, [], [], [x.sub.0]) (16)

Donde x y fval corresponden al vector solucion y al maximo valor que puede alcanzar la funcion objetivo. En [20] se encuentra mayor informacion sobre el uso del toolbox de optimizacion.

En la Tabla 6 se registran los valores correspondientes al BW optimoPL (PL), BW-Shapley (Sh), [X.sub.1] y [X.sub.2] que corresponden a la diferencia entre el BW solicitado por cada nodo ([d.sub.i]) y el BW asignado a traves de los metodos de PL y Shapley respectivamente; los cuales se encuentran asociados acorde a cada condicion de canal especifico.

Con el fin de evaluar, si el uso del valor de Shapley como estrategia de optimizacion en una red PLC realiza un mejor proceso de asignacion de recursos que el metodo de optimizacion-PL, se plantean las siguientes hipotesis:

[H.sub.o] : [[my].sub.(dBW-Op)] = [[my].sub.(dBW-Sh)]

[H.sub.a] : [[my].sub.(dBW-Op)] [desigual a] [[my].sub.(dBW-Sh)]

Donde [[my].sub.dBW-Op] y [[my].sub.dBW-Sh] son las medias correspondientes a la diferencia existente entre el BW solicitado y el BW asignado, a traves de los metodos de optimizacion-PL y el valor de Shapley respectivamente. La hipotesis [H.sub.o], plantea que existe igualdad entre las medias y la [H.sub.a] establece que existe una diferencia significativa entre medias, en donde el valor [[my].sub.dBW-Sh] es inferior al [[my].sub.dBW-Op], con lo cual se aceptaria que el uso del valor de Shapley realiza un proceso de optimizacion mas adecuado que el proceso de optimizacion proporcional, debido a que el valor asignado es mas cercano al Bit-rate solicitado.

Para aceptar o rechazar las hipotesis planteadas se hara uso de la prueba denominada t pareada [21], la cual es utilizada comunmente para evaluar la validez estadisitica de la diferencia entre dos muestras aleatorias. La expresion establecida para esta prueba estadistica es la siguiente (17).:

[t.sub.calculado] = [bar.d]/[S.sub.n][square root of (n)] (17)

Donde [S.sub.D], corresponde a la desviacion estandar en [dS.sup.2.sub.D] = [[suma de].sup.n.sub.i=1] [[[d.sub.i] - [bar.d]].sup.2]/[n - 1] y d es la diferencia entre las variables [X.sub.1] y [X.sub.2]. Para calcular el valor critico ([t.sub.critico]) se recurre al uso de Tablas de distribucion t student con n - 1 grados de libertad. Mediante el uso del programa estadistico Minitab [22] se realizo la prueba t pareada para las dos muestras con un ? - 0, 05 y 35 grados de libertad, acorde con los valores registrados en la Tabla 6, en donde se obtuvo el siguiente resultado:
T pareada para X1-X2                  Media del
                                          Error
             N    Media   Desv.Est.    estandar
X1           36    8.23       14.14        2.36
X2           36    6.05       11.65        1.94
Diferencia   36    2.19        8.24        1.37

IC de 95% para la diferencia media:: (-0,60; 4,97)
Prueba t de diferencia media = 0 (vs. no = 0):
Valor T = 1.59 Valor P = 0.121


El resultado indica un valor [t.sub.calculado] = 1.59 y un P - Valor = 0.121. Como el valor de [t.sub.calculado] < [t.sub.critico] (2.03), se acepta la [H.sub.o], lo cual es reforzado con el P - Valor; el cual presenta un valor superior a a - 0,05. Considerando lo anterior, se puede concluir que el valor de Shapley puede ser considerado como una excelente alternativa para realizar procesos de optimizacion para la asignacion de recursos en una red PLC, teniendo en cuenta que dentro del proceso de comparacion de tratamientos con un proceso de optimizacion sobre PL no se evidenciaron diferencias significativas entre sus medias.

4 Conclusiones

Ante la necesidad de realizar una distribucion equitativa de recursos, acorde con la demanda del servicio, entre los nodos que forman parte de una red PLC, se propuso el uso de la teoria de juegos cooperativos de utilidad transferible como estrategia de optimizacion para la asignacion recursos, con el fin de maximizar el Bit-rate en funcion de las necesidades de cada nodo. La propuesta surgio teniendo en cuenta que la teoria de juegos cooperativos se ha convertido en una herramienta de gran importancia a la hora de analizar situaciones en las cuales se requieren tomar decisiones, con una multiplicidad de respuestas posibles, a traves del modelamiento de estrategias optimas que le permitan maximizar su utilidad. Adicionalmente, el hecho de considerar que los nodos puedan trabajar cooperativamente aumenta la probabilidad de obtener una ganancia superior frente a la obtenida de actuar individualmente, en donde basta solo con conocer la utilidad que puede obtener cada coalicion y el vector pagos asociado. En todos los casos se considero cada escenario propuesto como un juego de bancarrota definido como una terna (N, d, C) donde N = {1, 2, 3 ... n} es el conjunto jugadores, d = {[d.sub.1], [d.sub.2], ..., [d.sub.n]} con [d.sub.i] > 0, [atane a todos]i [elemento de] N es el vector de demandas y C corresponde al valor neto que se debe repartir entre los elementos de N, con el fin de establecer cada una de las imputaciones del juego y con ello proceder a estimar el vector de pagos resultante acorde con las condiciones del canal PLC. En vista de lo anterior y con base en los resultados obtenidos se pudo evidenciar que el valor de Shapley arrojo excelentes resultados en relacion con la asignacion de recursos, estableciendo para cada nodo valores muy cercanos al valor requerido y bajo condiciones de saturacion de canal. Adicionalmente, se observo que la suma total correspondiente al Bit-rate asignado a cada jugador coincide con la capacidad total disponible en el canal PLC, acorde con las tres condiciones del canal (excelente, regular y deficiente).

El valor de Shapley puede ser considerado como una estrategia para asignacion de recursos en sistemas embebidos de bajo costo, como adaptadores PLC, debido a que no requiere hacer uso de operaciones matematicas complejas. Sin embargo, aunque el calculo directo del valor del Shapley presenta una complejidad temporal O(n[2.sup.n]) [13], es importante buscar la posibilidad de implementar algoritmos u otras tecnicas relacionadas con la distribucion de recursos, que presenten una cuota temporal mas baja en futuros trabajos de investigacion. Entre los algoritmos mas utilizados para calcular el valor de Shapley se encuentran el de Hart y Max-Colell y el denominado dividendo de Harsanyi los cuales presentan una complejidad temporal de O(n[2.sup.n]) y O([3.sup.n]) respectivamente [13].

Agradecimientos

El presente trabajo de investigacion ha sido desarrollado por el grupo de Investigacion DAVINCI de la Universidad Nacional Abierta y a Distancia con el apoyo de la Universidad Pontificia Bolivariana.

Referencias

[1] K. y. Y. L. y. G. S. Latchman Haniph y Srinivas, Homeplug AV and IEEE 1901: A Handbook for PLC Designers and Users, 1st ed. New Jersey, USA: Wiley-IEEE Press, 2013. 190, 197

[2] N. Anatory, J. y Theethayi, Broadband Power-Line Communication Systems: Theory and Applications., 1st ed. Southampton, England: WIT Press, 2010. 190

[3] J. L. y. T. E. C. Perez J y Jimeno, Teoria de juegos, 1st ed. Madrid, Espana: Pearson-Prentice Hall, 2003. 191, 194

[4] D. Ramirez R., "Cooperacion en la cadena de suministro de la energia electrica en Colombia," Tesis de Maestria, Universidad del Norte, 2008. 191

[5] P. Peleg B y Sudholter, Introduction to the theory of cooperative games. Springer, 2007. [Online]. Available: http://dx.doi.org/10.1007/978-3-540-72945-7 191, 192

[6] B. O'Neill, "A problem of rights arbitration from the Talmud," Mathematical Social Sciences, vol. 2, no. 4, pp. 345-371, 1982. [Online]. Available: http://dx.doi.org/10.1016/0165-4896(82)90029-4 191, 193

[7] H. Moulin, "Axiomatic Cost and Surplus-Sharing," in The Handbook of Social Choice and Welfare. Elsevier B.V., 2001, ch. 6, pp. 289-357. [Online]. Available: http://dx.doi.org/10.1016/S1574-0110(02)80010-8 191

[8] M. Aumann Robert J y Maschler, "Game theoretic analysis of a bankruptcy problem from the Talmud," Journal of Economic Theory, vol. 36, no. 2, pp. 195-213, 1985. [Online]. Available: http://dx.doi.org/10.1016/0022-0531(85) 90102-4 191

[9] I. Curiel, Cooperative game theory and applications: cooperative games arising from combinatorial optimization problems. Dordrecht: Kluwer Academic Publishers, 1997. 191

[10] M. y. V. A. Herrero C y Maschler, "Individual rights and collective responsibility: the rights egalitarian solution," Mathematical Social Sciences, vol. 37, no. 1, pp. 59-77, 1999. 191

[11] W. Thomson, "Axiomatic and game-theoretic analysis of bankruptcy and taxation problems: a survey," 2003. [Online]. Available: http: //dx.doi.org/10.1016/S0165-4896(02)00070-7 191

[12] M. L. C. Rodriguez, Contribuciones a la teoria del valor en juegos en forma estrategica y en problemas de bancarrota, S. d. P. e. I. Cientifico, Ed. Universidad Santiago de Compostela, 2005. 192

[13] J. R. F. Garcia, "Complejidad y algoritmos en juegos cooperativos," Tesis Doctoral, Universidad de Sevilla, 2000. 192, 209

[14] L. S. Shapley, "A value for n-persons games in Contributions to the Theory of Games II," Annals of Mathematics Studies, no. 28, pp. 307-317, 1953. 193

[15] A. Magana, "Formacion de coaliciones en los juegos cooperativos y juegos con multiples alternativas," Tesis Doctoral, Universidad Politecnica de Cataluna, 1996. [Online]. Available: http://www.tdx.cat/handle/10803/6700 193

[16] D. B. Gillies, "Some theorems on n-person games," Tesis Doctoral, Princeton University, 1953. 194

[17] L. S. Shapley, "On balanced sets and cores," Naval research logistics quarterly, vol. 14, no. 4, pp. 453-460, 1967. [Online]. Available: http://dx.doi.org/10.1002/nav.3800140404 194

[18] F. Canete, "User guide for PLC channel generator v. 2," 2011. [Online]. Available: http://www.plc.uma.es/channel_generator/User_guide_v2.pdf 196

[19] J. A. Cortes, "Modulation and Multiple Access Techniques for Indoor Broadband Power-Line Communications," Tesis Doctoral, Universidad de Malaga, 2007. [Online]. Available: http://www.biblioteca.uma.es/bbldoc/ tesisuma/17114500.pdf 196

[20] P. Berens, "CircStat: a MATLAB toolbox for circular statistics," Journal of Statistics Software, vol. 31, no. 10, pp. 1-21, 2009. [Online]. Available: http://www.jstatsoft.org/v31/i10/paper 206

[21] R. H. y. M. S. L. Walpole RE y Myers, Probabilidad y estadistica para ingenieros. Mexico D.F., Mexico: Pearson-Prentice Hall, 2007. 207

[22] Minitab Inc, "Pareto chart basics," 2015. [Online]. Available: http://support.minitab.com/en-us/minitab/17/topic-library/ quality-tools/quality-tools/pareto-chart-basics/ 208

Juan C. Vesga Ferreira (1), Gerardo Granados Acuna (2) y Javier E. Sierra Carrillo (3)

Recepcion: 02-12-2014 | Aceptacion: 04-05-2015 | En linea: 31-07-2015

MSC: 91A12,90C26 | PACS: 02.50.Le, 84.40.Ua, 02.50.Le

doi: 10.17230/ingciencia.11.22.9

(1) Universidad Nacional Abierta y a Distancia, Bucaramanga, Colombia, juan.vesga@unad.edu.co.

(2) Universidad Nacional Abierta y a Distancia, Bucaramanga, Colombia, gerardo.granados@unad.edu.co.

(3) Universidad Pontificia Bolivariana, Medellin, Colombia, javier.sierra@upb.edu.co.
Tabla 1: Bit-rate solicitado por cada nodo i

[Nodo.sub.i]   BW Solicitado [d.sub.i] [Mbps]

1                                        7.23
2                                       19.90
3                                        3.41
4                                        1.45
5                                        3.10
6                                       17.80
7                                        8.01
8                                        9.38
9                                        3.36
10                                      17.28
11                                      14.14
12 (CCo)                               105.15
Total                                  210.31

Tabla 2: Valor de utilidad transferible para cada una de las
coaliciones v(S)

Coalicion   Valor [*1e + 6]   Coalicion   Valor [*1e + 6]

{1}              0.00            {7}           0.00
{2}              0.00            {8}           0.00
{3}              0.00            {9}           0.00
{4}              0.00           {10}           0.00
{5}              0.00           {11}           0.00
{6}              0.00           {12}           0.00

Gran        {1,2,3,4,5,6,7,8,9,10,11,12}      159.72
coalicion

Tabla 3: Metodologia para estimar los valores de la matriz de Shapley
para 5 jugadores

        Contribucion a la coalicion que contiene j jugadores
        [v.sub.i,j] = v(S) - v (S - {i})

Jug.i   1                     2                   3

1       V(1)-V([fi])   [V(1,2)-V(2)] +   [V(1,2,3)-V(2,3)] +
                       [V(1,3)-V(3)] +   [v(1,2,4)-V(2,4)] +
                       [V(1,4)-V(4)] +   [V(1,2,5)-V(2,5)] +
                       [V(1,5)-V(5)]     [V(1,3,4)-V(3,4)] +
                                         [V(1,3,5)-V(3,5)] +
                                         [V(1,4,5)-V(4,5)]
2       V(2)-V([fi])   [V(1,2)-V(1)] +   [V(1,2,3)-V(1,3)] +
                       [V(2,3)-V(3)] +   [V(1,2,4)-V(1,4)] +
                       [V(2,4)-V(4)] +   [V(1,2,5)-V(1,5)] +
                       [V(2,5)-V(5)]     [V(2,3,4)-V(3,4)] +
                                         [V(2,3,5)-V(3,5)] +
                                         [V(2,4,5)-V(4,5)]
3       V(3)-V([fi])   [V(1,3)-V(1)] +   [V(1,2,3)-V(1,2)] +
                       [V(2,3)-V(2)] +   [V(1,3,4)-V(1,4)] +
                       [V(3,4)-V(4)] +   [V(1,3,5)-V(1,5)] +
                       [V(3,5)-V(5)]     [V(2,3,4)-V(2,4)] +
                                         [V(2,3,5)-V(2,5)] +
                                         [V(3,4,5)-V(4,5)]
4       V(4)-V([fi])   [V(1,4)-V(1)] +   [V(1,2,4)-V(1,2)] +
                       [V(2,4)-V(2)] +   [V(1,3,4)-V(1,3)] +
                       [V(3,4)-V(3)] +   [V(1,4,5)-V(1,5)] +
                       [V(4,5)-V(5)]     [V(2,3,4)-V(2,3)] +
                                         [V(2,4,5)-V(2,5)] +
                                         [V(3,4,5)-V(3,5)]
5       V(5)-V([fi])   [V(1,5)-V(1)] +   [V(1,2,5)-V(1,2)] +
                       [V(2,5)-V(2)] +   [V(1,3,5)-V(1,3)] +
                       [V(3,5)-V(3)] +   [V(1,4,5)-V(1,4)] +
                       [V(4,5)-V(4)]     [V(2,3,5)-V(2,3)] +
                                         [V(2,4,5)-V(2,4)] +
                                         [V(3,4,5)-V(3,4)]

p (j)   0.200               0.050               0.033

        Contribucion a la coalicion que contiene j jugadores
        [v.sub.i,j] = v(S) - v (S - {i})

Jug.i              4                    5         [[fi].sub.i](v)

1       [V(1,2,3,4)-V(2,3,4)] +   V(1,2,3,4,5)    [[fi].sub.1](v)
        [V(1,2,3,5)-V(2,3,5)] +   -V(2,3,4,5)
        [V(1,2,4,5)-V(2,4,5)] +
        [V(1,3,4,5)-V(3,4,5)]

2       [V(1,2,3,4)-V(1,3,4)] +   V(1,2,3,4,5)-   [[fi].sub.2] (v)
        [V(1,2,3,5)-V(1,3,5)] +   V(1,3,4,5)
        [V(1,2,4,5)-V(1,4,5)] +
        [V(2,3,4,5)-V(3,4,5)]

3       [V(1,2,3,4)-V(1,2,4)] +   V(1,2,3,4,5)-   [[fi].sub.3](v)
        [V(1,2,3,5)-V(1,2,5)] +   V(1,2,4,5)
        [V(1,3,4,5)-V(1,4,5)] +
        [V(2,3,4,5)-V(2,4,5)]

4       [V(1,2,3,4)-V(1,2,3)] +   V(1,2,3,4,5)-   [[fi].sub.4](v)
        [V(1,2,4,5)-V(1,2,5)] +   V(1,2,3,5)
        [V(1,3,4,5)-V(1,3,5)] +
        [V(2,3,4,5)-V(2,3,5)]

5       [V(1,2,3,5)-V(1,2,3)] +   V(1,2,3,4,5)-   [[fi].sub.5](v)
        [V(1,2,4,5)-V(1,2,4)] +   V(1,2,3,4)
        [V(1,3,4,5)-V(1,3,4)] +
        [V(2,3,4,5)-V(2,3,4)]

p (j)            0.050                0.200

Tabla 4: Matriz de Shapley para el escenario propuesto

            Contribucion a la coalicion que contiene j
            jugadores [*lE+8]

[J.sub.i]     1       2       3       4        5        6

1            0.0     0.0     0.7     3.6      12.3     25.6
2            0.0     0.2     2.0     10.9     35.7     70.6
3            0.0     0.0     0.3     1.6      5.6      12.1
4            0.0     0.0     0.1     0.7      2.3      5.1
5            0.0     0.0     0.3     1.5      5.1      11.0
6            0.0     0.1     1.8     9.7      31.7     62.8
7            0.0     0.0     0.8     4.0      13.7     28.3
8            0.0     0.0     0.9     4.7      16.1     33.3
9            0.0     0.0     0.3     1.6      5.5      11.9
10           0.0     0.1     1.7     9.4      30.7     60.9
11           0.0     0.1     1.4     7.6      25.0     49.8
12           0.5     7.0    40.5    137.2    304.0    458.1

[P.sub.j]   0.083   0.007   0.001   0.0005   0.0003   0.0002

            Contribucion a la coalicion que
            contiene j jugadores [*lE+8]

[J.sub.i]     7        8        9       10

1            31.1     23.6     11.9     3.9
2            84.9     65.0     32.9    10.9
3            14.8     11.2     5.6      1.8
4            6.3      4.7      2.3      0.8
5            13.5     10.2     5.1      1.7
6            75.5     57.9     29.3     9.7
7            34.4     26.2     13.2     4.4
8            40.3     30.6     15.4     5.1
9            14.5     11.0     5.5      1.8
10           73.4     56.2     28.5     9.5
11           60.1     46.0     23.3     7.7
12          477.1    346.0    173.5    57.8

[P.sub.j]   0.0002   0.0003   0.0005   0.001

            Contribucion a la coalicion que
            contiene j jugadores [*lE+8]

[J.sub.i]    11      12     [[fi].sub.i] (v)

1            0.8     0.0          4.6
2            2.2     0.2          13.0
3            0.3     0.0          2.2
4            0.1     0.0          0.9
5            0.3     0.0          2.0
6            1.9     0.1          11.6
7            0.8     0.0          5.2
8            1.0     0.0          6.0
9            0.3     0.0          2.1
10           1.9     0.1          11.2
11           1.5     0.1          9.2
12          11.5     1.0          91.3

[P.sub.j]   0.007   0.083        159.7

Tabla 5: BW solicitado y BW asignado (Shapley) para un estado de
canal excelente, regular y deficiente

                            BW Asignado [[fi].sub.i] (v) [Mbps]

Nodo i    BW Solicitado     Excelente   Regular   Deficiente
         [d.sub.i] [Mbps]

1              7.23           4.69       3.79        3.36
2             19.99           13.03      10.30       9.44
3              3.41           2.21       1.79        1.58
4              1.45           0.94       0.76        0.67
5              3.11           2.01       1.63        1.44
6             17.80           11.60      9.20        8.37
7              8.01           5.20       4.19        3.73
8              9.38           6.09       4.91        4.37
9              3.36           2.18       1.76        1.55
10            17.28           11.26      8.94        8.12
11            14.14           9.21       7.36        6.61
12            105.15          91.30      66.02      34.35
(CCo)

Total         210.31         159.72     120.65      83.59

Tabla 6: BW optimo-PL vs BW-Shapley acorde al estado de canal

                          Canal Excelente           Canal Regular

Ni   BW        PL     Sh    [X.sub.1]   [X.sub.2]    PL     Sh
     Solic.

1     7.2     5.9    4.7       1.3         2.5      4.6    3.8
2     20.0    14.4   13.0      5.6         7.0      10.2   10.3
3     3.4     2.9    2.2       0.5         1.2      2.7    1.8
4     1.5     1.2    0.9       0.3         0.5      1.4    0.8
5     3.1     2.6    2.0       0.5         1.1      2.5    1.6
6     17.8    12.9   11.6      4.9         6.2      9.2    9.2
7     8.0     6.5    5.2       1.5         2.8      4.9    4.2
8     9.4     7.4    6.1       1.9         3.3      5.5    4.9
9     3.4     2.9    2.2       0.5         1.2      2.7    1.8
10    17.3    12.6   11.3      4.7         6.0      9.0    8.9
11    14.1    10.5   9.2       3.6         4.9      7.6    7.4
12   105.2    79.9   91.3     25.3        13.9      60.3   66.0

          Canal Regular                Canal Deficiente

Ni   [X.sub.1]   [X.sub.2]    PL     Sh    [X.sub.1]   [X.sub.2]

1       2.7         3.4      3.2    3.4       4.0         3.9
2      11.5         4.1      6.9    9.4      13.1        10.6
3       2.0         1.1      1.9    1.6       1.5         1.8
4       0.8         0.4      1.2    0.7       0.3         0.8
5       1.8         1.0      1.8    1.4       1.3         1.7
6      10.2         3.7      6.2    8.4      11.6         9.4
7       4.6         2.3      3.5    3.7       4.5         4.3
8       5.4         2.5      3.9    4.4       5.5         5.0
9       1.9         1.1      1.9    1.6       1.5         1.8
10      9.9         3.7      6.1    8.1      11.2         9.2
11      8.1         3.2      5.2    6.6       8.9         7.5
12     60.3        13.9      41.8   34.4     63.4        70.8
COPYRIGHT 2015 Universidad EAFIT
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2015 Gale, Cengage Learning. All rights reserved.

 
Article Details
Printer friendly Cite/link Email Feedback
Author:Vesga Ferreira, Juan C.; Granados Acuna, Gerardo; Sierra Carrillo, Javier E.
Publication:Ingenieria y Ciencia
Date:Jul 1, 2015
Words:7738
Previous Article:Ingenieria y ciencia.
Next Article:Ajuste de la eficiencia de difraccion para el registro de hologramas a color de alta calidad.
Topics:

Terms of use | Privacy policy | Copyright © 2018 Farlex, Inc. | Feedback | For webmasters